C++刷leetcode（剑指 Offer II 039. 直方图最大矩形面积）【递增栈】
本帖最后由 糖逗 于 2022-12-18 13:26 编辑题目描述：
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights =
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights =
输出： 4
提示：
1 <= heights.length <=105
0 <= heights <= 104
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/0ynMMM
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res = 0;
stack<int> store;
store.push(-1);
for(int i = 0; i < heights.size(); i++){
while(store.size() > 1 && heights > heights){
int height = heights;
store.pop();
int width = i - store.top() - 1;
res = max(res, height * width);
}
store.push(i);
}
while(store.size() > 1){
int height = heights;
store.pop();
int width = heights.size() - store.top() - 1;
res = max(res, height * width);
}
return res;
}
}; {:5_108:} 6
页:
[1]