本文涉及知识点

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]为最低点的最长竖直线。
u p [ r ] [ c ] = { m a t [ r ] [ c ] 0 = = r 0 e l s e m a t [ r ] [ c ] = = 0 u p [ r − 1 ] [ c ] + 1 o t h e r up[r][c]=\begin{cases} mat[r][c] && 0 == r \\ 0&& else mat[r][c]==0 \\ up[r-1][c]+1 && other \\ \end{cases} up[r][c]=⎩ ⎨ ⎧​mat[r][c]0up[r−1][c]+1​​0==relsemat[r][c]==0other​
枚举各行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);
		}