# 1840. Maximum Building Height
###### tags: `Leetcode` `Hard` `Greedy` `Two Pass`
Link: https://leetcode.com/problems/maximum-building-height/description/
## 思路
先考虑那些有限制的位置
可以用[0135. Candy](https://hackmd.io/JkqMiZmmShydlXFmOl77bQ)的方法, 那么可以先从左往右扫一遍，根据```h[i-1]```来制约```h[i]```, 接下来我们再从右往左扫一遍，根据```h[i+1]```来进一步限制```h[i]```

这两遍操作的本质是什么呢？本质是：对于h数组中任意相邻的两幢楼，如果存在高度差，那么这个高度差是合理的！（也就是```h[i]```与```h[i-1]```的高度差不能超过```pos[i]-pos[i-1]```）。也就是说，此时的h数组是符合条件的安排。

我们再看一下，这两遍pass本身都是必要条件，即每个```h[i]```都不允许更高。但是最终我们神奇地发现，这个结果又是充分的。这说明我们得到了```h[i]```的最优解（即允许的最大值）。

现在我们已经优化了所有的```h[i]```，那么如何处理每个```h[i]```之间的那些没有高度限制的楼呢？很显然，我们会将```h[i]```往右不断增1，同时```h[i+1]```往左不断增1，查看这个peak会有多高。注意，我们保证了```h[i]```和```h[i+1]```的高度差是不超过```pos[i+1]-pos[i]```的，所以这个peak是一定存在的。我们可以这么计算，令peak距离```h[i]```是x，距离```h[i+1]```是y，则

h[i]+x = h[i+1]+y
pos[i]+x = pos[i+1]-y

可以知道这个peak的高度等于```h[i]+x = h[i+1]+y = ((h[i]-h[i+1]) - (pos[i]-pos[i+1))/2```

我们把每个间隔的peak都算出来取最大值。特别注意，```h```数组的最后一个楼往后，还有楼可以继续不停高度增一，记得补上```h[m]+n-pos[m]```
## Code

class Solution {
    public int maxBuilding(int n, int[][] restrictions) {
        int len = restrictions.length;
        int[][] newr = new int[len+1][2];
        newr[0] = new int[]{1,0};
        for(int i=0; i<len; i++) newr[i+1] = restrictions[i];
        Arrays.sort(newr, (a,b)->(a[0]-b[0]));
        int[] h = new int[len+1];
        for(int i=1; i<len+1; i++){
            h[i] = Math.min(h[i-1]+newr[i][0]-newr[i-1][0], newr[i][1]);
        }
        for(int i=len-1; i>=1; i--){
            h[i] = Math.min(h[i], h[i+1]+newr[i+1][0]-newr[i][0]);
        }
        int ans = 0;
        for(int i=1; i<len+1; i++){
            int y = ((h[i-1]-h[i]) - (newr[i-1][0]-newr[i][0]))/2;
            ans = Math.max(h[i]+y, ans);
        }
        ans = Math.max(ans, h[len] + n - newr[len][0]);
        return ans;
    }
}