题解 | #直方图内最大矩形#

思路：使用两个vector来记录左边最远到达的位置，和右边最远达到的位置；

在求解左边最远到达位置和右边最远到达位置时，使用单调栈的做法。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        // write code here
        int n = heights.size();
        vector<int> left(n);
        vector<int> right(n);
        stack<int> stk1;
        stack<int> stk2;
        
        for(int i=0; i<n; i++){
            while(!stk1.empty() && heights[stk1.top()] >= heights[i]){
                stk1.pop();
            }
            left[i] = stk1.empty() ? -1 : stk1.top();
            stk1.push(i);
        }
        
        for(int i=n-1; i>=0; i--){
            while(!stk2.empty() && heights[stk2.top()] >= heights[i]){
                stk2.pop();
            }
            right[i] = stk2.empty() ? n : stk2.top();
            stk2.push(i);
        }
        
        int area = 0;
        for(int i=0; i<n; i++){
            area = max(area, heights[i]*(right[i] - left[i] - 1));
        }
        return area;
    }
};