LeetCode84-柱状图中最大的矩形

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/largest-rectangle-in-histogram/

中文链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

题目详述

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

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

1
2
输入: [2,1,5,6,2,3]
输出: 10

题目详解

  • 维护一个单调栈，栈中元素从栈底到栈顶单调递增（存的是下标，比较用对应的值）。
  • 为了方便结算，提前 push 一个下标 -1。
  • 从左往右遍历数组，如果当前元素小于栈顶元素，弹出元素进行结算直至当前元素不小于栈顶元素。之后 push 当前下标。
  • 假设当前元素下标为 i，栈顶元素下标为 top，则当前矩形面积为 heights[top] * (i - stack.peek() - 1))。
  • 最后注意结算栈中剩余的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00084 {

    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 为了方便结算，提前 push 一个下标 -1
        stack.push(-1);
        int res = 0;
        for (int i = 0; i < heights.length; ++i) {
            while (stack.peek() != -1 && heights[i] < heights[stack.peek()]) {
                int top = stack.pop();
                res = Math.max(res, heights[top] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        // 结算栈中剩余的元素
        while (stack.peek() != -1) {
            int top = stack.pop();
            res = Math.max(res, heights[top] * (heights.length - stack.peek() - 1));
        }
        return res;
    }
}