day64 单调栈part03

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

求在该柱状图中，能够勾勒出来的矩形的最大面积。
在这里插入图片描述
看了一圈最后还是别的题解几句话看明白了明确一点，遍历每个高度，是要以当前高度为基准，寻找最大的宽度组成最大的矩形面积那就是要找左边第一个小于当前高度的下标left，再找右边第一个小于当前高度的下标right 那宽度就是这两个下标之间的距离了但是要排除这两个下标所以是right-left-1 用单调栈就可以很方便确定这两个边界了题解讲了很多但是貌似没有点明为什么这么做

这个博主讲得很清楚：
https://www.bilibili.com/video/BV1Me4y187T4/?spm_id_from=333.337.search-card.all.click&vd_source=8de9da7c303c17dad841c1520f0bb72b

// 单调栈方法
// 本质就是每一根柱子为中心能画出的最大矩形是往左和往右能找到的比自己高的柱子（必须是连着的），
// 也就是说，向左右找，找到柱子比自己矮为止，就是它的左右边界了，为了边界省心，可以左右添加一个0,最右边添加0也是为了方便弹出所有元素，因为遍历到最右边的0时，0小于栈顶元素，栈顶就要弹出，直到弹出所有，只剩首尾两个0
// 因为是单调递增栈，所以入栈的元素（栈顶）比栈里它的上一个元素大，相当于找到了左边界，然后继续找右边界
class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] newHeights = new int[heights.length + 2]; // 两边加一个0，简化运算
        for (int i = 0; i < heights.length; i++) newHeights[i + 1] = heights[i];
        Stack<Integer> stack = new Stack<>();
        stack.add(0);
        int res = 0;
        heights = newHeights; //注意这里已经换了哈

        // 第一个元素已经入栈，从下标1开始
        for (int i = 1; i < heights.length; i++) {
            if (heights[i] > heights[stack.peek()]) { // 大于栈顶，入栈
                stack.add(i); // add 和push都可以？ 
            } else if (heights[i] == heights[stack.peek()]) { // 等于栈顶,入栈
                //stack.pop();
                stack.push(i);
            } else { // 小于栈顶,弹出
                while (heights[i] < heights[stack.peek()]) {
                    int mid = stack.peek();
                    stack.pop();
                    int left = stack.peek(); // 左边界
                    int right = i; // 右边界
                    int w = right - left - 1; //宽度
                    int h = heights[mid]; //高度
                    res = Math.max(res, w*h);
                }
                stack.add(i);
            }

            
        }
        return res;
    }
}

// 双指针
class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        int[] minLeftIndex = new int [length];
        int[] minRightIndex = new int [length];
        // 记录左边第一个小于该柱子的下标
        minLeftIndex[0] = -1 ;
        for (int i = 1; i < length; i++) {
            int t = i - 1; // 先指向自己左边一个，看它比不比自己低
            // 这里不是用if，而是不断向右寻找的过程
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t]; // 如果发现比较的这个家伙，假如他叫a,比自己还高，那就直接去找比他还低的那个索引去比较，这样可以跳过很多比a还高的家伙
            minLeftIndex[i] = t;
        }
        // 记录每个柱子右边第一个小于该柱子的下标
        minRightIndex[length - 1] = length;
        for (int i = length - 2; i >= 0; i--) {
            int t = i + 1;
            while(t < length && heights[t] >= heights[i]) t = minRightIndex[t];
            minRightIndex[i] = t;
        }
        // 求和
        int result = 0;
        for (int i = 0; i < length; i++) {
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            result = Math.max(sum, result);
        }
        return result;
    }
}