【单调栈】【区间合并】LeetCode85:最大矩形

作者推荐

【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

本文涉及的知识点

单调栈区间合并

题目

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = [[“0”]]
输出：0
示例 3：
输入：matrix = [[“1”]]
输出：1
参数范围：
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 ‘0’ 或 ‘1’

分析

时间复杂度O(n²m)。枚举矩形的left和right，时间复杂度o(n^2)。指定left,right，计算连续1的数量大于等于width的行数，时间复杂度O(m)。

代码

核心代码

class Solution {
public:
	int maximalRectangle(vector<vector<char>>& matrix) {
		m_r = matrix.size();
		m_c = matrix.front().size();
		vector<vector<int>> vRightLen(m_r, vector<int>(m_c));
		for (int r = 0; r < m_r; r++)
		{
			for (int c = m_c - 1; c >= 0; c--)
			{
				if ('1' == matrix[r][c])
				{
					vRightLen[r][c] = 1 + ((m_c - 1 == c) ? 0 : vRightLen[r][c + 1]);
				}
			}
		}
		int iRet = 0;
		for (int left = 0; left < m_c; left++)
		{
			for (int right = left; right < m_c; right++)
			{
				const int width = right - left + 1;
				int height = 0;
				for (int r = 0; r < m_r; r++)
				{
					if (vRightLen[r][left] < width)
					{
						iRet = max(iRet, height * width);
						height = 0;
					}
					else
					{
						height++;
					}
				}
				iRet = max(iRet, height * width);
			}
		}
		return iRet;
	}
	int m_r, m_c;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	vector<vector<char>> matrix;
	int r;
	{
		Solution slu;		
		matrix = { {'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'} };
		auto res = slu.maximalRectangle(matrix);
		Assert(6, res);
	}
	{
		Solution slu;
		matrix = { {'0'} };
		auto res = slu.maximalRectangle(matrix);
		Assert(0, res);
	}
	{
		Solution slu;
		matrix = { {'1'} };
		auto res = slu.maximalRectangle(matrix);
		Assert(1, res);
	}
	{
		Solution slu;
		matrix = { {'1','1'}};
		auto res = slu.maximalRectangle(matrix);
		Assert(2, res);
	}
	{
		Solution slu;
		matrix = { {'1'},{'1' } };
		auto res = slu.maximalRectangle(matrix);
		Assert(2, res);
	}
}

单调栈

枚举底部，本题就可以转化成柱形图的最大矩形

class Solution {
public:
	int maximalRectangle(vector<vector<char>>& matrix) {		
		m_c = matrix.front().size();
		vector<int> vHeights(m_c);
		int iRet = 0;
		for (int r = 0; r < matrix.size(); r++)
		{
			for (int c = m_c - 1; c >= 0; c--)
			{
				if ('1' == matrix[r][c])
				{
					vHeights[c] +=1 ;
				}
				else
				{
					vHeights[c] = 0 ;
				}
			}
			iRet = max(iRet, largestRectangleArea(vHeights));
		}
		return iRet;
	}
	int largestRectangleArea(vector<int>& heights) {
		m_c = heights.size();
		vector<pair<int, int>> vLeftHeightIndex;
		vector<int> vLeftFirstLess(m_c, -1), vRightFirstMoreEqual(m_c, m_c);//别忘记初始化
		for (int i = 0; i < m_c; i++)
		{
			while (vLeftHeightIndex.size() && (heights[i] <= vLeftHeightIndex.back().first))
			{
				vRightFirstMoreEqual[vLeftHeightIndex.back().second] = i;
				vLeftHeightIndex.pop_back();
			}
			if (vLeftHeightIndex.size())
			{
				vLeftFirstLess[i] = vLeftHeightIndex.back().second;
			}
			vLeftHeightIndex.emplace_back(heights[i], i);
		}
		int iRet = 0;
		for (int i = 0; i < m_c; i++)
		{
			iRet = max(iRet, heights[i] * (vRightFirstMoreEqual[i] - vLeftFirstLess[i] - 1));
		}
		return iRet;
	}
	int m_c;
};

2022年12月版代码

 class Solution {
 public:
	 int maximalRectangle(vector<vector<char>>& matrix) {
		 m_r = matrix.size();
		 m_c = matrix[0].size();
		 vector<vector<int>> leftNums;
		 leftNums.assign(m_r, vector<int>(m_c));
		 for (int r = 0; r < m_r; r++)
		 {
			 for (int c = 0; c < m_c; c++)
			 {
				 if ('0' == matrix[r][c])
				 {
					 leftNums[r][c] = 0;
				 }
				 else
				 {
					 leftNums[r][c] = 1 + ((c > 0) ? leftNums[r][c - 1] : 0);
				 }
			 }
		 }
		 		 
		 for (int c = 0; c < m_c; c++)
		 {
			 stack<pair<int, int>> sta;			 
			 for (int r = 0; r < m_r; r++)
			 {
				 int iMinR = r;
				 while (sta.size() && (sta.top().first > leftNums[r][c]))
				 {
					 PopStack(sta, iMinR, r);
				 }
				 if (sta.empty() || (sta.top().first < leftNums[r][c]))
				 {
					 sta.emplace(leftNums[r][c], iMinR);
				 }
			 }
			 
			 while (sta.size())
			 {
				 int iMinR = m_r;
				 PopStack(sta, iMinR, m_r);
			 }
		 }
		 return m_iMaxArea;
	 }
	 void PopStack(stack<pair<int, int>>& sta,int& iMinRow,int r )
	 {
		 int iWidth = sta.top().first;
		 iMinRow = sta.top().second;

		 sta.pop();
		 m_iMaxArea = max(m_iMaxArea, iWidth*(r - 1 - iMinRow + 1));
	 }
	 int m_r, m_c;
	 int m_iMaxArea = 0;
 };