题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

题目

---

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

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

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

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

示例:

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

分析：
    题意：给定一个大小为n的非负整型数组，分别表示直方图的n个柱子高度，每个柱子宽度为1。返回该直方图所能形成的最大矩形面积。
    思路：这道题跟LeetCode 11很相似，但是因为考虑柱子宽度，因此解题技巧不相同，此题考查单调栈的应用。我们首先在数组最后加入0，这是为了方便处理完数组中的所有高度数据。假设存储高度坐标的栈为stack，当前处理的高度坐标为i(i∈[0→n])：① 如果当前stack为空，或者heights[i]大于等于栈顶坐标对应高度，则将i加入stack中；② 如果heights[i]小于栈顶坐标对应高度，说明可以开始处理栈内的坐标形成的局部递增高度，以求得当前最大矩形面积。弹出当前栈顶坐标 = top，此时栈顶新坐标 = top'，那么对应计算面积的宽度w = i - 1 - top'（若弹出栈顶坐标后，stack为空，则对应w = i），得到面积s = heights[top] * w，此时将i减一（因为进入循环i会加一，而待会儿需要重复考察第i个高度）；③ 遍历完成i∈[0→n]，返回最大矩形面积。

 

    时间复杂度为O(n)。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        // Exceptional Case: 
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return heights[0];
        }
        // insert 0 height
        heights.push_back(0);
        stack<int> st;
        int ans = 0;
        for(int i = 0; i <= n; i++){
            if(st.empty() || heights[i] >= heights[st.top()]){
                st.push(i);
            }
            else{
                int top = st.top();
                st.pop();
                int w = st.empty()? i: i - 1 - st.top();
                ans = max(ans, heights[top] * w);
                i--;
            }
        }
        return ans;
    }
};

 

————————————————
版权声明：本文为CSDN博主「prince谢晓峰」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/princexiexiaofeng/article/details/79652003