最大矩形

发表于 | 分类于 ，

单调栈遇到很多次了，我觉得这种类型的题目要是不会做的话就很吃亏，毕竟很经常出，而且理解之后也不是很难，关键是思路要捋清楚。

给一下题目：

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。（leetcode85 困难）

1
2
3
4
5
6
7
8
输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

##分析：

我一开始是按照动态规划的思路去尝试解答的，但是一直找不到状态转移的思路。确实是有类似的题型的，就是可以通过动态规划的思路去求解，稍微不太一样的点是它找的是矩阵中最大的子正方形（leetcode221 中等），也就是长和宽是一样的矩形，它的状态转移方程是：$dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1$

这里不太赘述了，之后如果遇到的话再深入理解吧，它这里二维dp还可以优化成一维dp。这是因为它的状态转移方程只用到了周围的信息（那之前很多不是很多都可以优化？）

正式分析啊，这一题可以看作是一题单调栈中的经典题型（leetcode84 困难）——柱状图中最大的矩形的延伸题，就是说我们可以直接使用找柱状图最大的矩形的解法来解我们这一题。怎么说呢，我们将原矩阵切片，从第一行往下切，按例题来说就是切四次。第二次就是切到第二行，然后将被切下来的矩阵转换成柱状图。怎么转换呢？从底往上数1的个数，注意是从底开始数哦，假设底为0，然后上面是1的话也不算的，那这一列的长度就为0了。这样我们可以得到一个柱状图，然后我们用leetcode84的解法可以得到这个柱状图的最大矩形，我们每切一次(新的柱状图）就得到一个最大矩形，我们留下最大的那个就是我们想要的结果了。所以我们首先要解决的问题就是在一个柱状图中找到一个最大的矩形。

在柱状图中找到最大的矩形

思路：要想找到在柱状图中的最大矩形，我们可以再往下想，以第i根柱子为最矮柱子所能延伸的最大面积是多少。这样通过比较所有柱子的最大面积，我们就可以得到柱状图中的最大矩形。稍微伪代码点的解释就是以i为中心，向左找第一个小于heights【i】的位置left_i;向右找第一个小于heights[i]的位置right_i，也就是最大面积heights[i]*（right_i-left_i-1)

所以我们的问题又变成如何找right_i和left_i。

#####如何找到right_i（右边第一个小于i的位置）和left_i

思路：暴力法肯定不行。我们这里使用单调栈来解决这个问题。

所谓单调栈就是单调递增或者递减的栈。两者有什么区别呢？
单调增：从栈底到栈顶是单调增加的，用于找到数组中某一位置的值的左边第一个小于它的位置以及右边第一个小于它的位置。

单调减：从栈底到栈顶是单调减少的，用于找到数组中某一位置的值的左边第一个大于它的位置以及右边第一个大于它的位置。

为什么单调栈有这种作用呢？那就要理单调栈的操作规则。

单调栈的操作规则：（以单调增为例）

1.如果新的元素比栈顶元素大，就入栈

2.如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小（注意，这里相等的话是不弹出来的，虽然这样部分柱子的最大面积计算出来是有误的，但不影响最后的结果，后面会解释。）

这样操作单调栈之后会发生什么呢？

1.栈内的元素是递增的

2.当元素出栈时，说明这个新元素（要入栈的）是出栈元素向右找第一个比其小的元素。

3.当元素出栈后，新栈顶元素是出栈元素向左找第一个比其小的元素。

（注意，这里都是针对出栈元素来比较的，所以对于最后的结果而言，我们原始的直方图的每个柱子进栈之后，最后都应该以出栈为结束，所以这里需要引入两个哨兵：在输入数组两个各放置1个0）

还需要注意的一点是栈中存储的是位置信息，不是值，在敲代码的时候一定要区分开，很容易搞乱掉···

放代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        # 放置哨兵
        heights = [0] + heights + [0]
        # 保留最佳结果
        res = 0
        for i in range(len(heights)):
            #print(stack)
            while stack and heights[stack[-1]] > heights[i]:
                tmp = stack.pop()
                # 每弹出一个元素，就计算这个元素的最大面积
                res = max(res, (i - stack[-1] - 1) * heights[tmp])
            # 由于最后一个元素是0，所以原始元素都会被弹出
            stack.append(i)
        return res

作者：powcai
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhao-liang-bian-di-yi-ge-xiao-yu-ta-de-zhi-by-powc/
来源：力扣（LeetCode）

之前说的数相等的情况，我们可以忽视计算错误的结果，因为最后弹出的相等的元素是不会计算错误的，而且它的面积也会是最大（在所有相等的元素的计算结果之中），就会覆盖掉之前计算错误的情况。

矩阵中找最大矩形

前面我们通过单调栈解决了在直方图中找最大矩形的问题，接下来我们就顺理成章地解决在矩阵找最大矩形的问题。直接上代码：(重点是后面那个函数)

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
class Solution:

    # Get the maximum area in a histogram given its heights
    def leetcode84(self, heights):
        stack = [-1]

        maxarea = 0
        for i in range(len(heights)):

            while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
                maxarea = max(maxarea, heights[stack.pop()] * (i - stack[-1] - 1))
            stack.append(i)

        while stack[-1] != -1:
            maxarea = max(maxarea, heights[stack.pop()] * (len(heights) - stack[-1] - 1))
        return maxarea


    def maximalRectangle(self, matrix: List[List[str]]) -> int:

        if not matrix: return 0

        maxarea = 0
        # 这里的dp存储的就是每一个直方图的高度（前面一个直方图计算完之后就会被后面的直方图覆盖掉）
        dp = [0] * len(matrix[0])
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):

                # update the state of this row's histogram using the last row's histogram
                # by keeping track of the number of consecutive ones

                dp[j] = dp[j] + 1 if matrix[i][j] == '1' else 0

            # update maxarea with the maximum area from this row's histogram
            maxarea = max(maxarea, self.leetcode84(dp))
        return maxarea

作者：LeetCode
链接：https://leetcode-cn.com/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode/
来源：力扣（LeetCode）

延伸

刚才的题目是递增栈的应用，递减栈的应用题目也是按这个思路来做：

题目描述：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2
解释：个子为4的可以看到个子为3的发型，个子为7可以看到个子为1的身高，所以1+1=2。

总结

总结一些常见的题目，比每次都错要好。

请作者喝杯咖啡吧！