※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 思路：
: 1.遍歷矩陣，找出任意一個點matrix[i][j]以這個點為結尾，上面共有多少個連續的1，
: 這就是這個點可以得到的最大高度。
: 2.因為最大的矩形面積一定是以這個點為中心不斷往左右兩邊擴展直到旁邊高度小於自己
: ，我們再對每一行依照高度進行排序，因為右邊所有元素都大於等於當前行的高，所以
: 面積 = 當前行高 * 當前到最右邊寬度
: 不斷用這個數值更新 res 即可。
看到討論區有 O(m*n) 也就是不用 sort 的解法
我一開始也想說幹怎麼可能
後來發現是用到這種最大高度的性質
如果自己的最大高度是 k 那往下一格的最大高度一定是 k+1 或 0
因為下一格只可能是 1 或 0
最大高度就只可能 +1 或直接變成 0
假設有連續兩個 row 每個 index 的最大高度像這樣
[6, 5, 4, 2, 2, 1, 1, 1, 0]
[7, 0, 5, 0, 3, 2, 2, 0, 1]
可以發現除了變成 0 的那些點外 其它的順序都維持的跟原本一樣
所以如果第一個 row 已經 sort 好
第二個 row 就不用再 sort 一次 直接把那些變成 0 的 index 塞到最後就好
只是要確保把單一 index 移到最後這個操作是 O(1) 例如用 double linked list
然後因為一開始大家的最大高度都是 0 或是 1
所以 sort 也不用到 O(nlogn)
Python code:
class Solution:
def largestSubmatrix(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
order = list(range(n))
res = 0
for i in range(m):
nextorder = [-1]*n
s, t = 0, n-1
for idx in order:
if matrix[i][idx]:
nextorder[s] = idx
s += 1
matrix[i][idx] += matrix[i-1][idx] if i > 0 else 0
res = max(res, matrix[i][idx]*s)
else:
nextorder[t] = idx
t -= 1
order = nextorder
return res