Leetcode84（柱状图中最大的矩形）

代码：

暴力解法（超时

class Solution {
    public int largestRectangleArea(int[] heights) {
        int area = heights[0];
        int n = heights.length;
        for(int i=0;i<n;i++){
            int min = heights[i];
            for(int j=i;j<n;j++){
                min = Math.min(min,heights[j]);
                area = Math.max(area,heights[i]);
                area = Math.max(area,min*(j-i+1));
            }
        }
        return area;
    }
}

题解里的 用栈存两边边界的数字

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for(int i=0;i<n;i++){
            while(!mono_stack.isEmpty()&&heights[mono_stack.peek()]>=heights[i]){
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty()?-1:mono_stack.peek());
            mono_stack.push(i);
        }
        mono_stack.clear();
        for(int i=n-1;i>=0;i--){
            while(!mono_stack.isEmpty()&&heights[mono_stack.peek()]>=heights[i]){
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty()?n:mono_stack.peek());
            mono_stack.push(i);
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            ans = Math.max(ans,(right[i]-left[i]-1)*heights[i]);
        }
        return ans;
    }
}