题目描述

---

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：

输入： heights = [2,4]
输出： 4

提示：

1 <= heights.length <=105
0 <= heights[i] <= 104

题解

---

暴力

---

部分测试用例通不过，因为O(N^2)的时间复杂度。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        //挨个遍历
        int maxNum = 0;
        for(int i = 0;i < heights.size();++i)
        {
            if(heights[i] == 0) continue;

            int result = 0;
            int height = heights[i];
            for(int j = 0;j < heights.size();++j)
            {
                if(heights[j] >= height)
                {
                    //取height周围的举行
                    result += height;
                }
                else
                {
                    //若遇到矮的则结束计算
                    maxNum = max(maxNum,result);
                    result = 0;//往后需要重新计算result
                    continue;
                }
            }
            maxNum = max(maxNum,result);
        }

        return maxNum;
    }
};
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
28
29
30
31
32

单调栈

---

每次遍历到heights[i]的时候，实际上我们已经能够判断出前面以heights[0~i-1]当中有哪些点为高的已经不满足了，此时我们可以通过栈来存取先前点，若是碰到矮的，我们就可以通过i - 栈顶的下标 O（1）操作确认宽度，且高度就是栈顶的高度。此时栈只需要添加i下标元素时依旧是单调递增即可。
栈当中存下标
处理可以分成两部：

• 第一次遍历的时候右边界是确定好的，所以可以直接求，左边界是pop后top的结果，因为前面可能出现更高的但是已经出栈的元素。
• 当遍历完后，栈不为空，此时右边界就是heights.size()，左边界就是栈顶的元素，最后一个元素是宽度是heights.size()

class Solution {
public:
    int largestRectangleArea(vector<int> heights) {
        //单调栈处理
        stack<int> st;
        int result = 0;
        //单调栈只存储下标，减少需要向前找宽度的过程
        for (int i = 0; i < heights.size(); ++i)
        {
            if (st.empty())
            {
                st.push(i);
            }
            else
            {
                if (heights[i] >= heights[st.top()])
                {
                    st.push(i);
                }
                else
                {
                    //这里相当于后面碰到更矮的，所以只用算前面的。
                    //表示当前元素比栈顶小，需要出栈顶元素 
                    //注意这里的左右边界的判定，左边界是pop后top的结果，右边界就是i
                    while (!st.empty() && heights[st.top()] > heights[i])
                    {
                        int tmp = 0;//临时面积
                        int cur = st.top();
                        st.pop();
                        int pre = -1;
                        if (!st.empty())
                        {
                            pre = st.top();
                        }

                        tmp += (i - pre - 1 ) * heights[cur];
                        result = max(result, tmp);
                    }
                    st.push(i);//这个元素也需要入栈
                }
            }
        }
        while (!st.empty())
        {
            int cur = st.top();
            st.pop();
            if (st.empty())
            {
                //只剩下最后一个元素
                int tmp = heights[cur] * heights.size();
                result = max(result, tmp);
            }
            else
            {
                //看前面元素在哪，就可以找到宽度
                int pre = st.top();
                //此时右边界不是cur，而是最右边
                int tmp = (heights.size() - 1 - pre) * heights[cur];
                result = max(tmp, result);
            }
        }
        return result;
    }
};
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

---

end

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论