LeetCode_085: Maximal Rectangle 动态规划

        这道题很难想,主要有两种解法,一种是把这道题目转化成之前那道(#084)直方图面积计算的题目,使用栈来做,但是还有更优雅的方法,使用DP。这两种方法的时间复杂度都是O(mn),空间复杂度都是O(n)。

题目

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

For example, given the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 6.

解法一:直方图面积

参考链接

行遍历,沿着这一行将矩阵切开,行上面的矩阵看做#84题目中的直方图,计算上面直方图面积的最大值。在遍历所有行之后,得到的面积最大值就是最大面积。

解法二:DP

参考链接

行遍历,沿着一行进行扫描,我们对于矩阵中的每个位置需要维护三个量:H 高度, L 左边界, R 右边界,这三个量将被用来计算一个矩形面积

0 0 0 1 0 0 0

0 0 1 1 1 0 0

0 1 1 1 1 1 0

我们来考虑上面的矩阵

在遍历第一行时,

高度H:0001000

遍历第二行时,只需要考虑前一行已存储的状态和这一行的值就可以了,直接在H的基础上修改就可以了

高度H:0012100

对于左右边界,情况复杂一点,需要考虑前一行存储的状态和这一行已扫面过的状态

遍历第一行时,

左边界L:0003000

遍历第二行时,

左边界L:0023200

在下面的代码中,使用curleft存储的值表示当前块的最左边,在最终决定左边界时,要考虑到上一行如果已经有已存在的左边界时,就选取上一行左边界值作为当前左边界(如第二行L的232中的3)。

这样每一行遍历时,内部就可以表示不同起始边界的矩形块了。

右边界同理。

该动态规划的过程就是利用了上一行的信息。

DP代码

一个容易理解的版本,后面还有一个做了代码优化的版本

class Solution {
public:
	int maximalRectangle(vector<vector<char>>& matrix) {
		int res = 0;
		const int m = matrix.size();
		if (m == 0){
			return 0;
		}
		const int n = matrix[0].size();
		if (n == 0){
			return 0;
		}

		vector<int> left(n, 0), right(n, n), height(n, 0);

		for (int i = 0; i < m; ++i){
			int cur_left = 0, cur_right = n;

			for (int j = 0; j < n; ++j){
				height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0; // ==1, 则height++,否则为0
			}

			for (int j = 0; j < n; ++j){
				left[j] = matrix[i][j] == '1' ? max(left[j], cur_left) : 0; // ==1 左边界 为 最右,否则为0
				cur_left = matrix[i][j] == '1' ? cur_left : j + 1; // ==1, 左边界不变,否则无效
			}

			for (int j = n - 1; j >= 0; --j){
				right[j] = matrix[i][j] == '1' ? min(right[j], cur_right) : n;
				cur_right = matrix[i][j] == '1' ? cur_right : j;
			}

			for (int j = 0; j < n; ++j){
				res = max(res, (right[j] - left[j]) * height[j]); // 计算面积
			}

		}
		return res;
	}
};

做了一些代码优化,6ms,轻松超过90%

class Solution {
public:
	int maximalRectangleCodeOP(vector<vector<char>>& matrix) {
		int res = 0;
		const int m = matrix.size();
		if (m == 0){
			return 0;
		}
		const int n = matrix[0].size();
		if (n == 0){
			return 0;
		}

		vector<int> left(n, 0), right(n, n), height(n, 0);

		for (int i = 0; i < m; ++i){
			int cur_left = 0, cur_right = n;

			for (int j = n - 1; j >= 0; --j){
				right[j] = matrix[i][j] == '1' ? min(right[j], cur_right) : n;
				cur_right = matrix[i][j] == '1' ? cur_right : j;
			}

			for (int j = 0; j < n; ++j){
				const bool flag = matrix[i][j] == '1';
				height[j] = flag ? height[j] + 1 : 0;
				left[j] = flag ? max(left[j], cur_left) : 0;
				cur_left = flag ? cur_left : j + 1;
				res = max(res, (right[j] - left[j]) * height[j]);
			}
		}
		return res;
	}
};

 

 

 

发表评论