[LeetCode Hot 100] LeetCode84. 柱状图中最大的矩形

题目描述

思路：枚举+优化(单调栈)

先固定矩阵的高。
然后向左向右找到第一个比当前元素值小的元素，确定好左右边界。

对于元素2来说：

• 向左找到第一个比当前元素值小的元素：1的右边界
• 向右找到第一个比当前元素值小的元素：3的右边界

枚举每个元素的上边界，确定往左数最远到达哪个边界(即寻找左边第一个比它小的数)，往右数最远到达哪个边界(即寻找右边第一个比它小的数)

思路总结：

1. 对于一个高度，如果能得到向左和向右的边界
2. 那么就能对每个高度求一次面积
3. 遍历所有高度，即可得出最大面积
4. 使用单调栈，在出栈操作时得到前后边界并计算面积

☆方法一：

class Solution {
    public int largestRectangleArea(int[] heights) {
        
        int[] left = new int[heights.length];
        Arrays.fill(left, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        // 计算每根柱子左边第一个小于这根柱子的柱子
        for (int i = heights.length - 1; i >= 0; i --) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                left[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        // 计算每根柱子左边第一个小于这根柱子的柱子
        int[] right = new int[heights.length];
        Arrays.fill(right, heights.length);
        stack = new ArrayDeque<>();
        for (int i = 0; i < heights.length; i ++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                right[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }

        int res = 0;
        for (int mid = 0; mid < heights.length; mid ++) {
            int height = heights[mid];
            res = Math.max(res, height * (right[mid] - left[mid] - 1));
        }
        return res;
    }
}

• left数组：初始化为-1
• right数组：初始化为lengths.length
• 宽度：right[i] - left[i] - 1
• 高度：heights[i]
• 时间复杂度：O(n)
• 空间复杂度：O(n)

从右开始遍历：求得左边界

for (int i = heights.length - 1; i >= 0; i --) {
	while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
		left[stack.peek()] = i;
		stack.pop();
	}
	stack.push(i);
}

从左开始遍历：求得右边界

for (int i = 0; i < heights.length; i ++) {
	while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
		right[stack.peek()] = i;
		stack.pop();
	}
	stack.push(i);
}

方法二：

class Solution {
    public int largestRectangleArea(int[] heights) {
        
        int[] left = new int[heights.length];
        Deque<Integer> stack = new ArrayDeque<>();
        // 计算每根柱子左边第一个小于这根柱子的柱子
        for (int i = 0; i < heights.length; i ++) {
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        // 计算每根柱子左边第一个小于这根柱子的柱子
        int[] right = new int[heights.length];
        Arrays.fill(right, heights.length);
        stack = new ArrayDeque<>();
        for (int i = heights.length - 1; i >= 0; i --) {
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? heights.length : stack.peek();
            stack.push(i);
        }

        int res = 0;
        for (int mid = 0; mid < heights.length; mid ++) {
            int height = heights[mid];
            res = Math.max(res, height * (right[mid] - left[mid] - 1));
        }
        return res;
    }
}

从左开始遍历：求得左边界

for (int i = 0; i < heights.length; i ++) {
	while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
		stack.pop();
	}
	left[i] = stack.isEmpty() ? -1 : stack.peek();
	stack.push(i);
}

从右开始遍历：求得右边界

for (int i = heights.length - 1; i >= 0; i --) {
	while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
		stack.pop();
	}
	right[i] = stack.isEmpty() ? heights.length : stack.peek();
	stack.push(i);
}

方法三：单调栈一次遍历

结合方法一和方法二，通过一次循环搞定。
需要保证两个for循环遍历的方向一致。