0085 - Maximal Rectangle
题干
破题
缝合一个简单类型和一个中等难度类型，就是LeetCode经典地困难类型题目。
简单型：
求最大“1”矩形面积，问题拆解地话，可以按行或者列进行统计1，统计每一行的列位置上“1”的高度，可以借用“滚动数组”的方法，用前一行的高度计算得到当前行的数据，这样把空间复杂度从 $O(nm)$ 降低为 $O(m)$ ：
当列位置值为“1”，就对前一行同一位置加一，否则置为零。
中等型：
这个中等型才是算法介绍的核心，如果计算一行地最大地直方图矩形。
假设我们已经知道了这一行的最大矩形，它一定有一个高度和宽度。
它的高度一定是这一行的某个位置的高度，而它的宽度一定是这个（或者这些位置中的某一个）位置所能达到的最大宽度。
解①DP：
以每个位置上的高度作为边，分别看它的前缀和后缀的所能到达的最大长度。
这里的做法就像 1340 - Jump Games V 里的做法，以前缀扫描为例（后缀同理），如果某个位置的前一个位置的高度不小于当前位置的高度，就加上这个位置的保存的前缀长度，然后继续探测，直到一个位置的高度小于当前位置高度，每向前多扫描一个位置，未来可能的扫描空间就减少一，总的时间复杂度 $O(m)$ 。
def solve(matrix: List[List[str]]) -> int:
n = len(matrix[0])
h = [0] * n
ans = 0
for row in matrix:
for i in range(n):
if row[i] == "1":
h[i] += 1
else:
h[i] = 0
pref = [1] * n
suff = [1] * n
for i in range(n):
if h[i]:
while i-pref[i] >= 0 and h[i-pref[i]] >= h[i]:
pref[i] += pref[i-pref[i]]
i2 = n-1-i
if h[i2]:
while i2+suff[i2] < n and h[i2+suff[i2]] >= h[i2]:
suff[i2] += suff[i2+suff[i2]]
ln_ans = max([(pref[i] + suff[i] - 1) * h[i] for i in range(n)])
if ln_ans > ans:
ans = ln_ans
return ans
时间复杂度 $O(nm)$ 。
运行时间：282 ms (beats 55.4%, ~100%)，内存占用：17.56 MB (beats 92.49%) 。
解②单调栈：
单调栈是标准解法。
这个思路并不显而易见，它的关键思路是： 分段统计 。
前面 DP 的解法计算的指标是矩形的边，而这里则直接关注它的高度，指标的统计依据这样的观察：
位于高度“波浪”上的较低点左边的、高度在其上的矩形，无法通过这个较低点来继续拓宽它的宽度2
也即，在较低点时可以统计它左边的、比它高的矩形面积。
技术上，我们用一个不减顺序的单调栈来保存极低点之前的坐标以用于满足条件的矩形面积的统计。
这样依次弹出所有高度不低于当前极低点的位置坐标，每弹出一个高度，需要弹出同等高度的所有坐标，然后计算这段宽度与高度的矩形面积，这样就统计了所极小点左边的，到极小点为止的矩形的面积。
之后再把当前极低点的坐标入栈。
这样如果在一行的高度数据的最后插入一个大小为 $0$ 的哨兵，确保单调栈最后一定会被清空，这样就统计了一行里面所有的矩形的面积。
def solve(matrix: List[List[str]]) -> int:
n = len(matrix[0])
h = [0] * (n+1) # sentinel: h[n] = 0
ans = 0
for row in matrix:
for i in range(n):
if row[i] == "1":
h[i] += 1
else:
h[i] = 0
stack = [-1] # sentinel: stack[0] = -1
for i in range(n+1):
while h[stack[-1]] > h[i]:
top = stack.pop()
while h[stack[-1]] == h[top]:
stack.pop()
cand = h[top] * (i-stack[-1]-1)
if ans < cand:
ans = cand
stack.append(i)
return ans
这里最精彩或者说最 Tricky 的地方是第二个“哨兵”的运用，一方面 -1 可以用作单调栈的基底，省却需要检测空的情况；另一方面，在 Python 的数组检索语法里，-1 又代表了列表的尾部元素，而记载高度的列表尾部是哨兵，正好是 $0$ ，可以直接用作大小的判断逻辑。
时间复杂度 $O(nm)$ 。
运行时间：234 ms (beats 97.39%, ~100%)，内存占用：17.65 MB (beats 70.19%) 。
注解
