柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（LeetCode）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

空间换时间

用minleftindex和minrightindex记录每个柱子左边和右边第一个比自己小的坐标

当前柱子的覆盖面积即为 r - l - 1

class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int len = heights.length;
        int[] minleftindex = new int[len]; //记录左边第一个小的坐标
        int[] minrightindex = new int[len]; //记录右边第一个小的坐标
        minleftindex[0] = -1;
        minrightindex[len-1] = len;
        for(int i = 1; i < len; i++){
           int l = i - 1;
           while(l >= 0 && heights[l] >= heights[i]){ //如果当前柱子小于等于左边的柱子
              //直接找左边柱子的第一个小的坐标，节省了遍历的时间
               l = minleftindex[l];
           }
           //heights[l] < heights[i];
           minleftindex[i] = l;
        }

        for(int i = len - 2; i >= 0; i--){
            int r = i + 1;
            while(r <= len-1 && heights[r] >= heights[i]){//如果当前柱子小于等于右边柱子
                //直接找右边柱子右边的第一个小的坐标，节省了遍历的时间
                r = minrightindex[r];
            }
            minrightindex[i] = r;
        }
        
        for(int i = 0; i < len; i ++){
            int w = minrightindex[i] - minleftindex[i] - 1;
            int h = heights[i];
            max = Math.max(max, w*h);
        }
        return max;
    }
}

单调栈

如图所示，遇到小于栈顶的元素的元素，就是栈顶元素右边第一个小于它的坐标r，左边第一个小于它的坐标就是栈顶左边的元素i，计算r - i -1 就是栈顶元素覆盖面积的宽度

遇到相同大小的元素也能入栈，如图计算完高度为6柱子的覆盖面积后，后续的两个5都会依次计算一次覆盖面积，故不影响结果

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] tall = new int[heights.length + 2];
        int len = tall.length;
        //左右边界补0，方便计算
        tall[0] = 0;
        tall[len-1] = 0;
        for(int i = 1; i <= len-2 ; i ++){
            tall[i] = heights[i-1];
        }

        
        Stack<Integer> st = new Stack<>(); // 单调栈，保证栈中元素单调增
        //那么，遇到小于栈顶的元素，开始出栈，该小于栈顶元素的坐标就是栈顶元素右边第一个小于的坐标
        //栈顶元素出栈后的下一个栈顶元素就是左边第一个小于该柱子的坐标
        int max = 0;
        st.push(0);
        for(int i = 1; i < len; i ++){
            if(tall[st.peek()] <= tall[i]){
                st.push(i);
            }else{
                while( !st.isEmpty() && tall[st.peek()] > tall[i]){//找到右边第一个小于的坐标
                    int index = st.pop();
                    int r = i; 
                    int l = index - 1;
                    if( !st.isEmpty()){
                        l = st.peek();
                    }
                    int w = r - l - 1;
                    int h = tall[index];
                    max = Math.max(max, w*h);
                }
                st.push(i);
            }
        }
        return max;
    }
}