https://programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html

1.本题是和上一个接雨水的题十分相似的题目，上一题是查找遍历过程中该元素左右的最大的值，单调栈单调增的操作，本题是找到最大的矩形，就像是短板原理一样，要找到最短的那个像左右连续扩展，一步一步找到最大的和，所以本题是在遍历过程中找到左右最近最小的值这样就可以通过遍历，将每一个值左右最近最小的值找到然后通过计算之间的间距和作为基础（底）的本层遍历的元素，这样就可以逐步找到最大的和。tips:本题为了避免特殊情况，也就是特殊的数组的影响类似于「2,4,6,8」或者「8,6,4,2」这样的数组会让我们在循环中无法找到对于的left或者right循环都结束了结果只是把数组下标原封不动的放进了栈里，这样的两种情况是不可以的，所以我们再开头和结尾都添加了一个0这样就可以保证无论是上面的两个特殊数组的哪一个都可以保证正常在循环中找到对于的左右的最近最小的值。

CPP

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int res = 0;
        st.push(0);
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        for(int i = 1; i < heights.size(); i++){
            while(!st.empty() && heights[i] < heights[st.top()]){
                int mid = st.top();
                st.pop();
                if(!st.empty()){
                    int left = st.top();
                    int right = i;
                    int h = heights[mid];
                    int w = right - left - 1;
                    res = max(res, h * w);
                }
            }
            st.push(i);
        }
        return res;
    }
};