Leetcode-84.柱状图中最大的矩形

发表于 分类于 阅读次数：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

1

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

 

示例:

输入: [2,1,5,6,2,3]
输出: 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：栈

维护一个单调递增栈，当i小于栈顶元素时出栈，记录对应高度

然后进行比较新栈顶位置与i组成的矩形面积和最大面积，

继续出栈直到i大于栈顶元素。

遍历数组结束后，处理栈中元素直到栈中只有标志位-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        st.push(-1);
        int n=heights.size();
        int i;
        int res=0;
        for(i=0;i<n;i++)
        {
            while(st.top()!=-1&&heights[st.top()]>heights[i])
            {
                int c=heights[st.top()];
                st.pop();
                res=max(res,(i-st.top()-1)*c);
            }
            st.push(i);
        }
        while(st.top()!=-1)
        {
            int c=heights[st.top()];
            st.pop();
            res=max(res,(i-st.top()-1)*c);
        }
        return res;
    }
};