【C++贪心单调栈】1727. 重新排列后的最大子矩阵|1926

本文涉及知识点

C++贪心
C++单调栈

LeetCode1727. 重新排列后的最大子矩阵

给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的列按任意顺序重新排列。
请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。
示例 1：
在这里插入图片描述

输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
输出：4
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。
示例 2：

在这里插入图片描述

输入：matrix = [[1,0,1,0,1]]
输出：3
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。
示例 3：
输入：matrix = [[1,1,0],[1,0,1]]
输出：2
解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。
示例 4：
输入：matrix = [[0,0],[0,0]]
输出：0
解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。
提示：
m == matrix.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] 要么是 0 ，要么是 1 。

枚举+贪心

up[r][c]记录以mat[r][c]为最低点的最长竖直线。
$up[r][c]=\begin{cases} mat[r][c] && 0 == r \\ 0&& else mat[r][c]==0 \\ up[r-1][c]+1 && other \\ \end{cases}$
枚举各行r，比较以r底的最大面积网格。heights = up[r]，heights中大于等于heights[c]的数量为x，则高为heights[c]的矩形最大宽带为x。将heights[i]排序后,x = n-i。
时间复杂度：O(mnlogn）

代码

核心代码

class Solution {
		public:
			int largestSubmatrix(vector<vector<int>>& matrix) {
				const int R = matrix.size();
				const int C = matrix.front().size();
				vector<int> pre(C);		
				int ans = 0;
				for (int r = 0; r < R; r++) {
					vector<int> dp;
					for (int c = 0; c < C; c++) {
						dp.emplace_back(matrix[r][c] ? (1 + pre[c]) : 0);
					}
					auto height = dp;
					sort(height.begin(), height.end());
					for (int i = 0; i < C; i++) {
						ans = max(ans, height[i] * (C - i));
					}
					pre.swap(dp);
				}
				return ans;
			}
		};

单元测试

	vector<vector<int>> matrix;
		TEST_METHOD(TestMethod11)
		{
			matrix = { {0,0,1},{1,1,1},{1,0,1} };
			auto res = Solution().largestSubmatrix(matrix);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			matrix = { {1,0,1,0,1} };
			auto res = Solution().largestSubmatrix(matrix);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			matrix = { {1,1,0},{1,0,1} };
			auto res = Solution().largestSubmatrix(matrix);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			matrix = { {0,0},{0,0} };
			auto res = Solution().largestSubmatrix(matrix);
			AssertEx(0, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功