Ricky.L的随笔
0%

LeetCode.84.柱状图中最大的矩形（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.84.柱状图中最大的矩形（困难）

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

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

题解

暴力枚举

暴力法虽然时间复杂度往往比较高，但是可以理清思路。

思路

就是枚举以每个柱子高度作为边长的最大矩形面积。

从每个柱子向左和向右检查是否有相同高度或更高的柱子，统计可以形成的矩形的最大宽度，然后计算面积，记录最大的。

复杂度

时间复杂度O(n ^ 2)：

  • 枚举所有柱子需要访问数组所有元素。
  • 一次中心扩散最坏情况下要访问数组所有元素，比如所有柱子高度相同。

空间复杂度O(1)：

  • 没有额外空间开销

暴力法多余的时间开销在哪？

中心扩散时，当前柱子的向右扩散，和后面柱子的向左扩散，这两个是重复的动作，应该优化。

应该怎么优化时间开销？

由于要查看每一个柱子高度能够形成多大面积的矩形，所以至少要遍历一次数组。

我们是从左到右遍历数组的，可以想办法避免向右扩散，只向左扩散来计算当前矩形面积，因为左边的柱子已经遍历过了。

那么现在问题变为：

  • 遇到什么样的柱子才能向左扩散？
  • 向左扩散时，左边的柱子什么时候计算以它们的高度为矩形边长的面积？

遇到什么样的柱子才能向左扩散？

  • 看暴力法中向右扩散的条件是，右边的柱子比当前柱子高，才需要扩散。
  • 那么右边柱子如果比当前柱子矮，就无法向右扩散，只能向左扩散。

向左扩散左边的柱子什么时候计算以它们的高度为矩形边长的面积？

在遇到不能向右扩散的柱子之前，所遍历过的柱子的特点是：它们高度是从左到右递增或相等的，否则就应该向左扩散了。

假设在遍历时，发现当前柱子比前一个柱子矮，设当前柱子是第i个。

以第i - 1个柱子高度构成的矩形面积怎么求？

  • 要寻找左右边界在哪。
  • 右边界是知道的，就是i，因为第i - 1个柱子的高度不能向右扩散了。
  • 左边界是i - 2，因为第i - 2个柱子到第i - 1个柱子的高度是递增的，第i - 1个柱子的高度不能向左扩散。

以第i - 2个柱子高度构成的矩形面积怎么求？

  • 左边界是i - 3，因为左边柱子高度是递增的。
  • 右边界在哪，要取决于第i - 2个柱子和第i个柱子哪个更高。
    • 如果第i - 2个柱子比第i个柱子高，右边界是i，因为第i - 2个柱子到第i - 1个柱子的高度是递增的，所以第i - 2个柱子可以把矩形扩散到比它高的柱子下面。
    • 如果第i - 2个柱子比第i个柱子矮，右边界不是i了，因为第i - 2个柱子的高度还可以向右扩散。
      • 什么时候可以计算以第i - 2个柱子高度的矩形面积呢？要在后面遇到比第i - 2个柱子矮的柱子才行，右边界就是后面那个矮柱子的索引，左边界是i - 3。

应该怎么记录左边柱子的信息？

  • 由于在遇到高度递减的柱子时，会求以左边柱子高度构成的矩形面积，而且并且有的柱子会求有的柱子不会求，所以要记录下所有没有求过矩形面积的柱子索引，并要能添加和移除，需要用一个集合保存。
  • 由于要访问左边柱子的高度，而遍历顺序是从左到右的，所以符合这个数据访问顺序的数据结构是栈。

边界处理

  • 计算第一个柱子高度的矩形面积时左边界是-1，取做边界的时候要特殊处理一下。
  • 如果末尾的柱子都是递增的，不会触发向左扩散，需要再遍历结束后手动触发一下。

复杂度

时间复杂度O(n)

  • 遍历一次数组需要访问n个元素。
  • 虽然访问栈需要往回看，但是入栈的元素都是不重复的，并且每个元素只会访问一次，往回看最多访问n个元素。

空间复杂度O(n)

最坏情况下，数组完全递增，栈最多保存n个元素。

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
import java.util.*

class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        val n = heights.size
        var maxArea = 0
        val stack = ArrayDeque<Int>()
        for (i in 0 until n) {
            while (stack.isNotEmpty() && heights[i] < heights[stack.peek()]) {
                val height = heights[stack.pop()]
                val right = i
                val left = if (stack.isNotEmpty()) stack.peek() else -1
                val width = right - left - 1
                val rectArea = width * height
                maxArea = maxOf(maxArea, rectArea)
            }
            stack.push(i)
        }

        // 触发末尾递增柱子的矩形面积计算
        while (stack.isNotEmpty()) {
            val height = heights[stack.pop()]
            val right = n
            val left = if (stack.isNotEmpty()) stack.peek() else -1
            val width = right - left - 1
            val rectArea = width * height
            maxArea = maxOf(maxArea, rectArea)
        }

        return maxArea
    }
}