C++刷leetcode（84. 柱状图中最大的矩形）【单调递增栈】
题目描述：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入:
输出: 10
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
stack<int> temp;
heights.insert(heights.begin(), 0);//因为right = i-1为了防止越界
heights.push_back(0);
for (int i = 0; i < heights.size(); i++)
{
while (!temp.empty() && heights > heights)
{
int cur = temp.top();
temp.pop();
int left = temp.top() + 1;
int right = i - 1;
ans = max(ans, (right - left + 1) * heights);
}
temp.push(i);
}
return ans;
}
页:
[1]