leetcode 1840 两次遍历消除局部限制

此题类似于135题,但要稍微绕点弯子。
此题需要考虑到,每个楼的高度限制实际是对周围的限制加了限制,理解到这个咱们就可以想到,用两次遍历解决这个问题。此外,楼之间最高的可能性可以通过数学方式计算,由于已经消除了不可能的情况,所以肯定能算出来。
假设两边为 ( i , a ) (i,a) (i,a) 和 ( j , b ) (j,b) (j,b),假设中间最高楼层是 c c c,那么可以得到公式 ( c − a − 1 ) + ( c − b − 1 ) = j − i (c-a-1)+(c-b-1)=j-i (c−a−1)+(c−b−1)=j−i
即可得到最终答案
c = f l o o r ( a + b + j − i 2 ) c = floor(\frac{a+b+j-i}{2}) c=floor(2a+b+j−i​)
最终要考虑的就是最右边的无线增长,看最右边的限制即可,代码如下:

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        if(restrictions.size() == 0)return n-1;

        restrictions.push_back(vector<int>{1, 0});
        sort(restrictions.begin(), restrictions.end());
        int m = restrictions.size();

        for(int i=1;i<m;i++)
        {
            int mx_height = restrictions[i-1][1] + restrictions[i][0] - restrictions[i-1][0];
            if(mx_height < restrictions[i][1])restrictions[i][1] = mx_height;
        }

        // 右限制,存最大值
        int ret = restrictions[m-1][1];
        ret = max(ret, n-restrictions[m-1][0]+restrictions[m-1][1]);
        for(int i=m-2;i>=0;i--)
        {
            int mx_height = restrictions[i+1][1] + restrictions[i+1][0] - restrictions[i][0];
            if(mx_height < restrictions[i][1])restrictions[i][1] = mx_height;
            ret = max(ret, restrictions[i][1]);
        }

        // 找中间的最大值
        for(int i=1;i<m;i++)
        {
            ret = max(ret, (restrictions[i][0]-restrictions[i-1][0]+\
                restrictions[i][1]+restrictions[i-1][1])/2);
        }

        return ret;
    }
};
上一篇:信息学奥赛一本通 1147:最高分数的学生姓名 | OpenJudge NOI 1.9 02


下一篇:Mx Player播放器去除升级提示