leetcode-1840. 最高建筑高度

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

在一座城市里，你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。

这座城市对这些新建筑有一些规定：

每栋建筑的高度必须是一个非负整数。
第一栋建筑的高度 必须 是 0 。
任意两栋相邻建筑的高度差 不能超过 1 。
除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 restrictions 的形式给出，其中 restrictions[i] = [idi, maxHeighti] ，表示建筑 idi 的高度 不能超过 maxHeighti 。

题目保证每栋建筑在 restrictions 中 至多出现一次 ，同时建筑 1 不会 出现在 restrictions 中。

请你返回 最高 建筑能达到的 最高高度 。

示例 1：

输入：n = 5, restrictions = [[2,1],[4,1]]
输出：2
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,1,2] ，最高建筑的高度为 2 。
示例 2：

输入：n = 6, restrictions = []
输出：5
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,3,4,5] ，最高建筑的高度为 5 。
示例 3：

输入：n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
输出：5
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,3,3,4,4,5,4,3] ，最高建筑的高度为 5 。

提示：

2 <= n <= 109
0 <= restrictions.length <= min(n – 1, 105)
2 <= idi <= n
idi 是 唯一的 。
0 <= maxHeighti <= 109

题解1
暴力，会超时，从后往前遍历出来能够到达的最大高度。

class Solution { 
   
public:
    bool cmp(vector<int>&a,vector<int>&b){ 
   
        return a[0] < b[0];
    }
    const int INF = 0x3f3f3f3f;
    int maxBuilding(int n, vector<vector<int>>& restrictions) { 
   
        sort(restrictions.begin(),restrictions.end());
        int res = 0;
        vector<int>maxheight(n,INF);
        int m = restrictions.size();
        for(int i = 0;i < m;i ++){ 
   
            restrictions[i][0] = restrictions[i][0] - 1;
            cout<<restrictions[i][0]<<" ";
        }
        cout<<endl;
        for(int i = m - 1;i >= 0;i --){ 
   
            int prepox = 0;
            if(i >= 1)prepox = restrictions[i - 1][0];
            else prepox = 0;
            int nowheight = min(maxheight[restrictions[i][0]],restrictions[i][1]);
            for(int j = restrictions[i][0];j >= prepox;j --){ 
   
                maxheight[j] = nowheight + restrictions[i][0] - j;
            }
        }
        for(int i = 0;i < n;i ++){ 
   
            cout<<maxheight[i]<<" ";
        }
        cout<<endl;
        int now = 0;
        for(int i = 1;i < n;i ++){ 
   
            now = min(maxheight[i],now + 1);
            res = max(res,now);
        }

        return res;
    }
};

方法2：
limit的传递性，从左从右各扫一遍。

class Solution { 
   
public:
    bool cmp(vector<int>&a,vector<int>&b){ 
   
        return a[0] < b[0];
    }
    const int INF = 0x3f3f3f3f;
    int maxBuilding(int n, vector<vector<int>>& restrictions) { 
   
        restrictions.push_back({ 
   1,0});
        sort(restrictions.begin(),restrictions.end());
        if(restrictions[restrictions.size() - 1][0] != n){ 
   
            restrictions.push_back({ 
   n,n - 1});
        }
        int m = restrictions.size();
        auto &&r = restrictions;
        for(int i = 1;i < m;i ++){ 
   
            r[i][1] = min(r[i][1],r[i - 1][1] + r[i][0] - r[i - 1][0]);
        }
        for(int i = m - 2;i >= 0;i --){ 
   
            r[i][1] = min(r[i][1],r[i + 1][1] + r[i + 1][0] - r[i][0]);
        }
        int res = 0;
        for(int i = 1;i < m;i ++){ 
   
            res = max(res,(r[i][1] + r[i - 1][1] + r[i][0] - r[i - 1][0]) / 2);
        }
        return res;
    }
};