LeetCode刷题笔记（贪心）：maximal-rectangle

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 1,192 | 阅读时长 ≈ 5

[toc]

题目描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

给定一个用0和1填充的2D二进制矩阵，找到包含所有1的最大矩形并返回其面积。

解题思路

刚看到这道题的时候，一脸无奈。我们还是先来看一下Largest Rectangle in Histogram这道题目吧。

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].



The largest rectangle is shown in the shaded area, which has area = 10 unit.



For example,
Given heights = [2,1,5,6,2,3],
return 10.

我们先把代码贴出来，然后边看代码边捋清思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        stack<int> s;
        height.push_back(0);//追加一个零用来做终止条件。
        int maxSize = 0;
        int i = 0; 
        while(i < height.size()){
            if(s.empty() || height[i] >= height[s.top()])
                s.push(i++);
            else{
                int cur = height[s.top()];
                s.pop();
                maxSize = max(maxSize, cur * (s.empty() ? i : i - 1 - s.top()));
            }
        }
        return maxSize;
    }
};
  • 首先，我们需要新建stack来保存遍历过程中的递增序列。如果栈是空的，那么索引i入栈。所以当i=0时，将0入栈。注意栈内保存的是索引，不是高度。然后i++。



  • 当i=1的时候，发现height[i]小于了栈内的元素，于是出栈。这时候stack为空，所以面积的计算是height[t] * i。t是刚刚弹出的stack顶元素。也就是蓝色部分的面积。



  • 这时候stack为空了，那就继续入栈。注意到只要是连续递增的序列，我们都要keep pushing，直到我们遇到了i=4，height[i]=2小于了栈顶的元素。



  • 这时候开始计算矩形面积。首先弹出栈顶元素，t=3。即下图绿色部分。



  • 接下来注意到栈顶的（索引指向的）元素还是大于当前i指向的元素，于是出栈，并继续计算面积，桃红色部分。



  • 最后，栈顶的（索引指向的）元素大于了当前i指向的元素，循环继续，入栈并推动i前进。直到我们再次遇到下降的元素，也就是我们最后人为添加的dummy元素0.



  • 同理，我们计算栈内的面积。由于当前i是最小元素，所以所有的栈内元素都要被弹出并参与面积计算。



注意我们在计算面积的时候已经更新过了maxSize 。

我们可以看到，stack中总是保持递增的元素的索引，然后当遇到较小的元素后，依次出栈并计算栈中bar能围成的面积，直到栈中元素小于当前元素。

maximal-rectangle

这道题的解法灵感来自于Largest Rectangle in Histogram这道题，假设我们把矩阵沿着某一行切下来，然后把切的行作为底面，将自底面往上的矩阵看成一个直方图（histogram）。直方图的中每个项的高度就是从底面行开始往上1的数量。根据Largest Rectangle in Histogram中的largestRectangleArea函数我们就可以求出当前行作为矩阵下边缘的一个最大矩阵。接下来如果对每一行都做一次Largest Rectangle in Histogram，从其中选出最大的矩阵，那么它就是整个矩阵中面积最大的子矩阵。算法时间复杂度为O(m*n)，这解法真是太棒了，其实应该算是动态规划的题目了。

C++版代码实现

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 {
public:
    
class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        stack<int> s;
        height.push_back(0);//追加一个零用来做终止条件。
        int maxSize = 0;
        int i = 0; 
        while(i < height.size()){
            if(s.empty() || height[i] >= height[s.top()])
                s.push(i++);
            else{
                int cur = height[s.top()];
                s.pop();
                maxSize = max(maxSize, cur * (s.empty() ? i : i - 1 - s.top()));
            }
        }
        return maxSize;
    }
};
    
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.empty())
            return 0;
        int maxRec = 0;
        vector<int> height(matrix[0].size(), 0);
        for(int i = 0; i < matrix.size(); ++i){
            for(int j = 0; j < matrix[0].size(); ++j){
                if(matrix[i][j] == '1')//这里的数字1一定要加单引号哦~
                    height[j]++;
                else
                    height[j] = 0;
            }
            maxRec = max(maxRec, largestRectangleArea(height));//对每一行都求一次最大值，而不是只有最后一行。
        }
        return maxRec;
    }
};

参考链接

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz

0%