84. 柱状图中最大的矩形-向日葵屋

84. 柱状图中最大的矩形

题目：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
目的：找到面积最大的矩形
面积 = 高度 * 宽度
高度确定，宽度不确定
1 暴力穷举法
思路：双指针。
1.1 左指针向左移动，直到第一个比自己矮的矩形
1.2 右指针向右移动，直到第一个比自己矮的矩形

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] arr = new int[len+2];
        for (int i = 0; i< heights.length; i++) {
            arr[i+1] = heights[i];
        }
        int ans = 0;
        for (int i = 1; i < arr.length-1; i++) {
            int currentHeight = arr[i];
            int left = i; 
            int right = i;
            while (left > 0 && arr[left] >= arr[i] ) {
                left--;
            }
            while (right < arr.length-1 && arr[right] >= arr[i]) {
                right++;
            }
            ans = Math.max(ans, currentHeight * (right - left-1));
        }
        return ans;
    }
}

2 单调栈
定义一个栈，指针向右移动，比自己高就入栈，直到遇到比自己低的矩形，不入栈，而是出栈，一直出到比自己矮的矩形

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 单调栈 https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/java-shuang-jie-fa-dai-ma-jian-ji-yi-dong-dan-diao/
        int len = heights.length;
        int[] arr = new int[len+2];
        for (int i = 0; i< len; i++) {
            arr[i+1] = heights[i];
        } 
        // heights [2, 1, 5, 6, 2, 3]
        // arr  [0, 2, 1, 5, 6, 2, 3, 0]
        int res = 0;
        int index = 1;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        while (index < arr.length) {
            while (index < arr.length && arr[index] >= arr[stack.peek()]) {
                stack.push(index);
                index++;
            }
            while (index < arr.length && arr[index] < arr[stack.peek()]) {
                int curHeight = arr[stack.pop()];
                res = Math.max(res, curHeight * (index - stack.peek() - 1));
            }
        }
        return res;
    }
}