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;
}
};