84. 柱状图中最大的矩形
1、双指针
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
# 左右第一个小于 i 的下标
min_l, min_r = [0] * n, [0] * n
res = 0
min_l[0] = -1
for i in range(1, n):
temp = i-1
while temp >= 0 and heights[temp] >= heights[i]:
temp = min_l[temp]
min_l[i] = temp
min_r[n-1] = n
for i in range(n-2, -1, -1):
tmp = i + 1
while tmp < n and heights[tmp] >= heights[i]:
tmp = min_r[tmp]
min_r[i] = tmp
for i in range(n):
area = heights[i] * (min_r[i] - min_l[i] - 1)
res = max(area, res)
return res
2、单调栈
# 找到左右第一个小于下标为 i 的
heights.insert(0, 0)
heights.append(0)
n = len(heights)
stack = []
res = 0
for i in range(n):
while stack and heights[i] < heights[stack[-1]]:
mid_h = heights[stack.pop()]
if stack:
area = (i - stack[-1] - 1) * mid_h
res = max(area, res)
stack.append(i)
return res