第十章 单调栈 part03 84. 柱状图中最大的矩形

第六十三天| 第十章 单调栈 part03 84. 柱状图中最大的矩形

一、84. 柱状图中最大的矩形

• 题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/

• 题目介绍：

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

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

    示例 1:

    

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

• 思路：

  • 本题和接雨水是相反的思路，接雨水是找左右最大的值，然后算凹槽的面积来接雨水。而本题是**找到左边第一个比它矮的和右边第一个比它矮的（当前元素是栈口元素），然后向左向右延伸**，求一个最大的面积。
  • 因此，本题的单调栈是单调递减的。
    • 此外，本题还有一个特殊的地方，就是要在原数组的头尾各插入一个0
      • 在尾部插入0是为了防止原数组是单调递增，那么放入栈中就是单调递减，无法触发当前元素小于栈顶元素的逻辑，也就无法计算面积
      • 在头部插入0是为了防止原数组是单调递减的，计算面积需要mid、left、right。如果本身数组就是单调递增的，那么栈中就没有第二个元素，即没有left，所以也无法计算面积。

• 代码：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int i = 0; i < heights.length; i++) {
            newHeights[i + 1] = heights[i];
        }
        heights = newHeights;
        int result = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int i = 1; i < heights.length; i++) {
            if (heights[i] >= heights[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                    int mid = stack.pop();
                    if (!stack.isEmpty()) {
                        int left = stack.peek();
                        int right = i;
                        int h = heights[mid];
                        int w = right - left - 1;
                        result = Math.max(result, h * w);
                    }
                }
                stack.push(i);
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32