欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数组-最大矩形-困难

程序员文章站 2022-07-07 15:54:36
...
描述
给你一个二维矩阵,权值为False和True,找到一个最大的矩形,使得里面的值全部为True,输出它的面积
您在真实的面试中是否遇到过这个题?  是
样例
给你一个矩阵如下
[
  [1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1]
]

输出6

题目链接

分析

数组-最大矩形-困难

根据上图,可以清楚的看出本题可以转化为Largest Rectangle in Histogarm来做初始化height = [0, 0 ,0 ....]对于每一行,先求出以这一行为x轴的每个柱子的高度,求解时,可以每次基于上一行的值进行更新。然后O(n)的时间求出最大矩形,不断更新全局变量res时间复杂度为 O(n * (n + n)) = O(n2)

程序


class Solution {
public:
	/**
	* @param matrix a boolean 2D matrix
	* @return an integer
	*/
	int maximalRectangle(vector<vector<bool> > &matrix) {
		// Write your code here
		if (matrix.empty() || matrix[0].empty()) {
			return 0;
		}

		int m = matrix.size();
		int n = matrix[0].size();

		vector<vector<int> > height(m, vector<int>(n, 0));
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (!matrix[i][j]) {
					height[i][j] = 0;
				}
				else {
					height[i][j] = (i == 0) ? 1 : height[i - 1][j] + 1;
				}
			}
		}

		int maxArea = 0;
		for (int i = 0; i < m; i++) {
			maxArea = max(maxArea, largestRectangleArea(height[i]));
		}
		return maxArea;
	}

	int largestRectangleArea(vector<int> &height) {
		vector<int> s;
		height.push_back(0);

		int sum = 0;
		int i = 0;
		while (i < height.size()) {
			if (s.empty() || height[i] > height[s.back()]) {
				s.push_back(i);
				i++;
			}
			else {
				int t = s.back();
				s.pop_back();
				sum = max(sum, height[t] * (s.empty() ? i : i - s.back() - 1));
			}
		}

		return sum;
	}
};