代码随想录算法训练营第六十天 | 单调栈 柱状图中最大的矩形 完结撒花

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

柱状图中最大的矩形

• 双指针解法
• 本题要记录记录每个柱子 左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。
• 在寻找的过程中使用了while

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] minLeftIndex = new int[heights.length];
        int[] minRightIndex = new int[heights.length];

        int length = heights.length;

        // 记录每个柱子，左边第一个小于该柱子的下标
        minLeftIndex[0] = -1; 
        for (int i = 1; i < length; i++) {
            int t = i - 1;
            while (t >= 0 && heights[t] >= heights[i]) {
                t = minLeftIndex[t];
            }
            minLeftIndex[i] = t;
        }

        // 记录每个柱子 右边第一个小于该柱子的坐标
        minRightIndex[length - 1] = length;  // 注意这里初始化，防止下面while死循环
        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;
    }
}

• 单调栈

• 栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
• 情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
• 情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
• 情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<>();

        // 数组扩容，在头尾各加入一个元素
        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;
        for (int i = 1; i < heights.length; i++) {
            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;
    }
}