leetcode-085

上周做完Largest Rectangle in Histogram后leetcode推荐我接下来做这一题，因此本周算法题就选它了。

题目

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

Example:
1
2
3
4
5
6
7
8
9
> Input:
> [
>   ["1","0","1","0","0"],
>   ["1","0","1","1","1"],
>   ["1","1","1","1","1"],
>   ["1","0","0","1","0"]
> ]
> Output: 6
>

分析

这道题的意思很明确，给出一个二维矩阵，让我们从中找出由1组成的最大矩形面积，和上周那题一样，都是要求最大矩形面积，但输入由一维数组变成了二维数组。

解法

如果采用暴力求解的话，我们可以先找出所有只由1组成的矩形(一个个遍历元素，从它开始向右、向下再向右扩展)，再从中计算出最大的矩形面积。但用暴力求解来解上周那一维输入的题运行时间都超了1000ms，这次肯定会超时，因此我没有采用这种解法。

实际上，这两道题之间有着很大的联系，不然我也不会一直提起上周那题。仔细想想，求解一维数组中最大矩形面积我们已经有了较快的解法，那么我们可以考虑把从二维数组求解转变成从一维数组求解。

我们从上往下，一行行来分解二维矩阵，就可以把问题转变成求m次一维数组的最大矩形面积(m为行数)：以一个一维数组来存放高度，当遍历到下一行时，从左往右遍历每一列位置，如果该位置为0，则高度为0；否则高度为上一行求得的高度+1。

例如，在例子中，遍历到每一行时高度分别为：

["1","0","1","0","0"],
["2","0","2","1","1"],
["3","1","3","2","2"],
["4","0","0","3","0"]

运用上一周的算法即可算出答案。

代码

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int maximalRectangle(vector<vector<char> >& matrix) {
        if (matrix.size() == 0) return 0;
        int result = 0;
        vector<int> heights(matrix[0].size(), 0);

        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[i].size(); ++j) {
                if (matrix[i][j] == '0') heights[j] = 0;
                else heights[j]++;
            }
            result = max(result, largestRectangleArea(heights));
        }
        return result;
    }

    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        int n = heights.size();
        if (n == 0) return 0;
        int left[n], right[n];
        left[0] = -1;
        right[n - 1] = n;
        for (int i = 1; i < n; ++i) {
            if (heights[i] > heights[i - 1]) left[i] = i - 1;
            else {
                //找第一个小于当前元素的元素下标
                int tmp = left[i - 1];
                while (heights[i] <= heights[tmp] && tmp != -1) {
                    tmp = left[tmp];
                }
                left[i] = tmp;
            }
        }
        for (int i = n - 2; i >= 0; --i) {
            if (heights[i] > heights[i + 1]) right[i] = i + 1;
            else {
                //找第一个小于当前元素的元素下标
                int tmp = right[i + 1];
                while (heights[i] <= heights[tmp] && tmp != n) {
                    tmp = right[tmp];
                }
                right[i] = tmp;
            }
            result = max(result, (right[i] - left[i] - 1) * heights[i]);
        }
        result = max(result, (right[n - 1] - left[n - 1] - 1) * heights[n - 1]);
        return result;
    }
};

static int x = []() { 
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    return 0; 
}();

复杂度分析

这个解法的复杂度重点在于求最大矩形面积的算法，在上周我们已经分析过，算法由于while循环的次数可以很少，因此算法时间复杂度可以逼近O(n)，空间复杂度O(2n) = O(n)。

因此这个解法的时间复杂度逼近O(mn)，空间复杂度为O(3n) = O(n)，其中m为matrix行数，n为matrix列数。

另外，在提交后查看别人的代码时，我发现了这么一段代码：

static int x = []() { 
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    return 0; 
}();

这段代码通过关闭cout与printf之间的同步、解除cin与cout之间的绑定提高了C++的IO效率。详情参见：

https://blog.csdn.net/chenf1999/article/details/84452273

在这么做之后，这个解法在leetcode上运行时间为8ms。