C++刷LeetCode（1727. 重新排列后的最大子矩阵）【数学】

糖逗

题目描述：

1. 给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的 列 按任意顺序重新排列。
   
2. 
   
3. 请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。
   
4. 
   
5.  
   
6. 
   
7. 示例 1：
   
8. 
   
9. 
   
10. 
    
11. 输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
    
12. 输出：4
    
13. 解释：你可以按照上图方式重新排列矩阵的每一列。
    
14. 最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。
    
15. 示例 2：
    
16. 
    
17. 
    
18. 
    
19. 输入：matrix = [[1,0,1,0,1]]
    
20. 输出：3
    
21. 解释：你可以按照上图方式重新排列矩阵的每一列。
    
22. 最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。
    
23. 示例 3：
    
24. 
    
25. 输入：matrix = [[1,1,0],[1,0,1]]
    
26. 输出：2
    
27. 解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。
    
28. 示例 4：
    
29. 
    
30. 输入：matrix = [[0,0],[0,0]]
    
31. 输出：0
    
32. 解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。
    
33.  
    
34. 
    
35. 提示：
    
36. 
    
37. m == matrix.length
    
38. n == matrix[i].length
    
39. 1 <= m * n <= 105
    
40. matrix[i][j]&#160;要么是&#160;0&#160;，要么是&#160;1 。
    
41. 
    
42. 来源：力扣（LeetCode）
    
43. 链接：https://leetcode-cn.com/problems/largest-submatrix-with-rearrangements
    
44. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     int len1, len2;
   
4. public:
   
5.     int largestSubmatrix(vector<vector<int>>& matrix) {
   
6.         len1 = matrix.size(), len2 = matrix[0].size();
   
7.         vector<vector<int> >store1 = matrix;
   
8.         for(int i = len1 -2; i >= 0; i--){
   
9.             for(int j = 0; j < len2; j++){
   
10.                 if(matrix[i][j] == 1)store1[i][j] = store1[i+1][j] + 1;
    
11.             }
    
12.         }
    
13.         int res = INT_MIN;
    
14.         for(int i = 0; i < len1; i++){
    
15.             vector<int>store2 = store1[i];
    
16.             sort(store2.begin(), store2.end());
    
17.             for(int j = 0; j < len2; j++){
    
18.                 int width = len2 - j;
    
19.                 res = max(res, store2[j] * width);
    
20.             }
    
21.         }
    
22.         return res;
    
23.     }
    
24. };

复制代码