Ricky.L的随笔
0%

LeetCode.85.最大矩形（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.85.最大矩形（困难）

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

题解

思路

如果以某一行为横轴，该行以上的列为纵轴区域，问题就转变为LeetCode.84.柱状图中最大的矩形（困难）。

某一行下，每一列下，与行相连的1的个数就是柱子高度。

整个求解过程

每行柱子高度统计方法优化

  • 如果到达每一行，再往上遍历遍历每列柱子高度，是有重复计算的。
  • 可以保存之前行的柱子高度的结果，在到下一行的时候，发现这一行某一列是1，就累加高度，是0就清空柱子高度，因为无法形成柱子。这样就不用重复计算了。
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*

class Solution {
    fun maximalRectangle(matrix: Array<CharArray>): Int {
        val m = matrix.size
        if (m == 0) return  0
        val n = matrix[0].size
        var maxArea = 0
        val heights = IntArray(n) { 0 }
        for (row in 0 until m) {
            for (col in 0 until n) {
                if (matrix[row][col] == '1') heights[col]++
                else heights[col] = 0
            }
            val area = largestRectangleArea(heights)
            maxArea = maxOf(maxArea, area)
        }
        return maxArea
    }

    private 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
    }
}

复杂度

时间复杂度O(mn)

m为矩阵行数，n为矩阵列数。

  • 求柱子高度需要遍历矩阵所有元素，所有元素有m*n个。
  • 求每个柱子高度需要O(n)。

空间复杂度O(n)

  • 高度数组占用O(n)。
  • 求柱子最大矩形面积需要O(n)的栈。