单调栈系列~LeetCode84.柱状图中最大的矩形（困难）

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int []left = new int[len];
        int []right = new int[len];
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<len; i++){//从前往后找当前元素后面的比他小的最小元素
            while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                stack.pop();
            }
            if(stack.isEmpty()){
                left[i] = -1;
            }else{
                left[i] = stack.peek();
            }
            stack.push(i);
        }
        stack.removeAllElements();//将栈中的元素清空
        for(int i=len-1; i>=0; i--){//从后向前找当前元素后面的比他小的最小元素
            while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                 stack.pop();
            }
            if(stack.isEmpty()){
                right[i] = len;
            }else{
                right[i] = stack.peek();
            }
            stack.push(i);
        }
        int max = 0;
        for(int i=0; i<len; i++){
            max = Math.max(max, heights[i] * (right[i] - left[i] - 1));
        }
        return max;
    }
}