算法打卡day52|单调栈篇03| 84.柱状图中最大的矩形

算法题

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

题目链接:84.柱状图中最大的矩形

大佬视频讲解：84.柱状图中最大的矩形视频讲解

个人思路

这题和接雨水是相似的题目，原理上基本相同，也是可以用双指针和单调栈解决，只是有些细节不同。

解法

双指针

相比接雨水，这道题难在要记录每个柱子左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。所以需要循环查找，其他思路与接雨水一样。

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;
            // 这里用while来不断向右寻找
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            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;
    }
}

时间复杂度:O(n)；（每个元素都执行了最多n次的比较操作）

空间复杂度:O( n);（minLeftIndex和minRightIndex暂存数据）

单调栈

本地单调栈的解法和接雨水的题目是类似的，接雨水是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。

所以这道题的单调栈里的顺序，应该是从大到小的顺序！

来举一个例子，如图：

只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。所以本题单调栈的顺序正好与接雨水反过来。

此时应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度

除了栈内元素顺序和接雨水不同，剩下的逻辑都差不多,代码如下

主要分析清楚如下三种情况：

情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

除此之外， height数组前后需要各加一个元素0，解释如下：

末尾需要要加元素0，因为如果数组本身就是升序的，例如[2,4,6,8]，那么入栈之后都是单调递减，一直都没有走，情况三计算结果的哪一步，所以最后输出的就是0了。那么结尾加一个0，就会让栈里的所有元素，走到情况三的逻辑。 如图：

开头也要加元素0，因为如果数组本身是降序的，例如 [8,6,4,2]，在 8 入栈后，6 开始与8 进行比较，此时得到 mid（8），rigt（6），但是得不到 left。因为将 8 弹出之后，栈里没有元素了，那么为了避免空栈取值，直接跳过了计算结果的逻辑。之后又将6 加入栈（此时8已经弹出了），然后就是 4 与栈口元素 8 进行比较，周而复始，那么计算的最后结果resutl就是0。如图所示：

class Solution {
    int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<Integer>();
        
        // 数组扩容，在头和尾各加入一个元素
        int [] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++){
            newHeights[index + 1] = heights[index];
        }

        heights = newHeights;
        
        st.push(0);
        int result = 0;

        // 第一个元素已经入栈，从下标1开始
        for (int i = 1; i < heights.length; i++) {
            // 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下标
            if (heights[i] > heights[st.peek()]) {
                st.push(i);
            } else if (heights[i] == heights[st.peek()]) {
                st.pop();
                st.push(i);
            } else {
                while (heights[i] < heights[st.peek()]) { //循环比较
                    int mid = st.peek();
                    st.pop();
                    int left = st.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = heights[mid];
                    result = Math.max(result, w * h);
                }
                st.push(i);
            }
        }
        return result;
    }
}