84. 柱状图中最大的矩形

题目链接

解题思路：

• 题目乍一看没有思路，那我们来想一想如果暴力求解怎么办。最大的矩形，他总有一个高(竖着的)，然后有一个宽(横着的)，那我们就暴力求解每一个高，也就是每一个下标i，对应的heights[i]，最大的宽是多少，然后求出所有的解后，最优的便是结果。
• 怎么求解以heights[i]为高，最大的宽是多少？用单调栈。单调栈是啥？简单来说就是，求i左边，比i「小的，离i最近的」在哪，求i右边，比i「小的，离i最近的」在哪。(当然，也可以求大的)
• 所以，我们就可以得到以heights[i]为高，然后得出最大的宽，这就是其中之一的结果。把所有结果得到之后，求最大的那个，就是最终的结果。

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;    // 栈底到栈顶是小到大   存的是下标
        int ans = 0;
        int n = heights.size();
        for (int i = 0; i < n; ++i) {
            while(!st.empty() && heights[i] < heights[st.top()]) {
                int wid_right = i;    // 宽的右边界
                int wid_left = 0;   // 宽的左边界
                int height = heights[st.top()];   // 高
                st.pop();
                if (!st.empty()) {    // 如果栈不为空  它下面压着的  就是左边 比他小 离他最近的
                    wid_left = st.top() + 1;
                }
                ans = max(ans, (wid_right - wid_left) * height);
            }
            st.push(i);
        }
        // 栈不空
        while(!st.empty()) {
            int wid_right = n;    // 宽的右边界  右边没有比当前栈顶小的了
            int wid_left = 0;    // 宽的左边界
            int height = heights[st.top()];
            st.pop();
            if (!st.empty()) {
                wid_left = st.top() + 1;
            }
            ans = max(ans, (wid_right - wid_left) * height);
        }
        return ans;
    }
};