807. 保持城市天际线【逻辑】
在二维数组grid中，grid[i][j]代表位于某处的建筑物的高度。 我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。 高度 0 也被认为是建筑物。
最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。 城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。
建筑物高度可以增加的最大总和是多少？
例子：
输入： grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出： 35
解释：
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]
从数组竖直方向（即顶部，底部）看“天际线”是：[9, 4, 8, 7]
从水平水平方向（即左侧，右侧）看“天际线”是：[8, 7, 9, 3]
在不影响天际线的情况下对建筑物进行增高后，新数组如下：
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
说明:
1 < grid.length = grid[0].length <= 50。
grid[i][j] 的高度范围是： [0, 100]。
一座建筑物占据一个grid[i][j]：换言之，它们是 1 x 1 x grid[i][j] 的长方体。
class Solution {
public:
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
int n=grid.size();
int m=grid[0].size();
vector<int> x(n,0);
vector<int> y(m,0);
for(int i=0;i<n;i++){
if(grid[i].size()>m){
y.resize(grid[i].size());
}
for(int j=0;j<grid[i].size();j++){
x[i]=max(x[i],grid[i][j]);
y[j]=max(y[j],grid[i][j]);
}
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<grid[i].size();j++){
ans+=min(x[i],y[j])-grid[i][j];
}
}
return ans;
}
};
- 直接计算就行
- 没有注意到
grid.length = grid[0].length是个正方形
218. 天际线问题【优先队列+扫描线】
城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。
每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：
lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
注意：输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]
示例 1：
输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。
示例 2：
输入：buildings = [[0,2,3],[2,5,3]]
输出：[[0,3],[5,0]]
提示：
1 <= buildings.length <= 104
0 <= lefti < righti <= 231 - 1
1 <= heighti <= 231 - 1
buildings 按 lefti 非递减排序
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
int n=buildings.size();
vector<vector<int>> ans;
vector<int> boundries;
auto cmp=[](const pair<int,int>&a, const pair<int,int>&b)->bool{return a.second<b.second;};
priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)>height(cmp);
for(auto b:buildings){
boundries.push_back(b[0]);
boundries.push_back(b[1]);
}
sort(boundries.begin(),boundries.end());
int i=0;int preHeight=0;
for(auto b:boundries){
while(i<n&&buildings[i][0]<=b){
//cout<<b<<' '<<i<<endl;
height.push(pair<int,int>(buildings[i][1],buildings[i][2]));
i++;
}
while(height.size()&&height.top().first<=b){
//cout<<b<<' '<<height.top().first<<endl;
height.pop();
}
int h=height.size()?height.top().second:0;
if(h!=preHeight){
vector<int> res;
res.push_back(b);
res.push_back(h);
ans.push_back(res);
preHeight=h;
}
}
return ans;
}
};
当你调用pop()时，实际上是弹出优先队列的序列中的最后一个数(back)，而这个被弹出的数也就是priority_queue的top()。也就是说，我们所认为的top()和pop()是获取、弹出优先级最高的数，实际上这个数就是当前优先队列序列中的最后一个数。
这似乎也就不难解释cmp比较函数与优先队列返回的最大值之间的关系了：以默认的比较函数less为例，它的作用是将较小的数放在前面，因此最大的数肯定就位于序列的末尾了，当调用top()函数时，返回末尾的数，也就是序列中最大的数，而pop()则弹出这个数，而这个数，通常被认为是“优先级最高”的数。
其实可以发现，这些比较函数都是当其返回true时，就把第一个参数放在第二个参数前面，从而完成排序，基本的原理都是大同小异的，并且可以发现，默认的排序方式都是按“<”来排序，也就是说默认比较函数会将原序列排为升序。
————————————————
版权声明：本文为CSDN博主「HerofH_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_28114615/article/details/86495567