LeetCode 84. 柱状图中最大的矩形

解题思路

单调栈经典题型，
    这道题我们需要找到heights[i]左边的最近的比heights[i]小的值，
找到heights[i]右边的最近的比heights[i]小的值。所以我们想到了单调栈。

相关代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Stack<Integer> stack = new Stack<>();
        int left[] = new int[n];
        for(int i=0;i<n;i++){
            while(stack.isEmpty()==false&&heights[stack.peek()]>=heights[i]) stack.pop();
            if(stack.isEmpty()==true) left[i]=-1;
            else left[i]=stack.peek();
            stack.push(i);
        }
        //清除栈中的所有元素
        while(stack.isEmpty()==false) stack.pop();
        int right[] = new int[n];
        for(int i=n-1;i>=0;i--){
            while(stack.isEmpty()==false&&heights[stack.peek()]>=heights[i]) stack.pop();
            if(stack.isEmpty()==true) right[i]=n;
            else right[i]=stack.peek();
            stack.push(i);
        }

        int res=0;
        for(int i=0;i<left.length;i++){
            res=Math.max(res,heights[i]*(right[i]-left[i]-1));
        }
        return res;
    }
}