→ SecondRun: 大師 11/26 15:25
推 wwndbk: 沒想到 大師 11/27 01:59
https://leetcode.com/problems/largest-submatrix-with-rearrangements/description
1727. Largest Submatrix With Rearrangements
給你一個二維陣列表示的矩陣 matrix[][]，我們可以任意交換矩陣裡的行，求出這個矩
陣由 1 組成的矩形最大面積為多少。
思路：
1.遍歷矩陣，找出任意一個點matrix[i][j]以這個點為結尾，上面共有多少個連續的1，
這就是這個點可以得到的最大高度。
2.因為最大的矩形面積一定是以這個點為中心不斷往左右兩邊擴展直到旁邊高度小於自己
，我們再對每一行依照高度進行排序，因為右邊所有元素都大於等於當前行的高，所以
面積 = 當前行高 * 當前到最右邊寬度
不斷用這個數值更新 res 即可。
Java Code：
------------------------------------------------
class Solution {
public int largestSubmatrix(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 1) {
matrix[i][j] += matrix[i - 1][j];
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
Arrays.sort(matrix[i]);
for (int j = 0; j < m; j++) {
res = Math.max(res, (m - j) * matrix[i][j]);
}
}
return res;
}
}
------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700983370.A.F90.html
※ 編輯: Rushia (122.100.73.13 臺灣), 11/26/2023 15:23:07