※ 引述《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

大师

太神了

大师