LeetCode—84.柱状图中最大的矩形[Largest Rectangle in Histogram]——分析及代码[C++]
一、题目二、分析及代码1. 栈（优化前）（1）思路（2）代码（3）结果
2. 栈（优化后）（1）思路（2）代码（3）结果
三、其他
一、题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例:
输入: [2,1,5,6,2,3]
输出: 10
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、分析及代码
1. 栈（优化前）
（1）思路
可以用一个栈处理遍历到矩形的位置和高度： 1）新矩形高度大于等于 top 时，存入矩形； 2）新矩形高度小于 top 时，依次 pop 栈中高度大于新矩形的矩形，并依次计算它们所组成的面积。（相当于将这些矩形超出目前新矩形的高度抹去）。
（2）代码
class Solution {
public:
int largestRectangleArea(vector
<int>& heights
) {
if (heights
.empty())
return 0;
int hsize
= heights
.size();
stack
<pair
<int, int>> h
;
int ans
= 0;
for (int i
= 0; i
< hsize
; i
++) {
if (h
.empty() || heights
[i
] > h
.top().first
- 1)
h
.push({heights
[i
], i
});
else {
int min_index
;
while (!h
.empty() && h
.top().first
> heights
[i
] - 1) {
ans
= max(ans
, h
.top().first
* (i
- h
.top().second
));
min_index
= h
.top().second
;
h
.pop();
}
h
.push({ heights
[i
], min_index
});
}
}
while (!h
.empty()) {
ans
= max(ans
, h
.top().first
* (hsize
- h
.top().second
));
h
.pop();
}
return ans
;
}
};
（3）结果
执行用时 ：16 ms, 在所有 C++ 提交中击败了 77.20% 的用户； 内存消耗 ：10.8 MB, 在所有 C++ 提交中击败了 8.78% 的用户。
2. 栈（优化后）
（1）思路
上述思路和实现过程有几处可优化： 1）在 heights 中，通过矩形的位置可以直接查到对应高度，因此栈中只需存储位置即可； 2）计算面积时可以采用栈中前一元素的下标，避免反复计算、存储被覆盖的最小下标； 3）可以通过在 heights 的末位 push 元素 0 ，使得处理最后栈中留下的矩形部分过程，可以和之前统一处理。
（2）代码
class Solution {
public:
int largestRectangleArea(vector
<int>& heights
) {
stack
<int> h
;
heights
.push_back(0);
int ans
= 0, hsize
= heights
.size();
for (int i
= 0; i
< hsize
; i
++) {
while (!h
.empty() && heights
[h
.top()] > heights
[i
]) {
int top
= h
.top();
h
.pop();
ans
= max(ans
, heights
[top
] * (h
.empty() ? i
: (i
- h
.top() - 1)));
}
h
.push(i
);
}
return ans
;
}
};
（3）结果
执行用时 ：8 ms, 在所有 C++ 提交中击败了 99.36% 的用户； 内存消耗 ：10.6 MB, 在所有 C++ 提交中击败了 27.86% 的用户。
三、其他
暂无。
