84. 柱状图中最大的矩形
- 思路
- example
- 暴力双指针（中心扩散）:
. 或者固定左边界方法，同样复杂度。
- 0 <= heights[i] <= 104
- 单调栈
- 栈递增 （list: 从左到右）
[2,1,5,6,2,3] extend to [0,2,1,5,6,2,3,0] （前后补0)
stack = [0] (实际stack存储元素下标）
stack = [0,2] heights[i] >= heights[stack[-1]]
stack = [0, 1] heights[i] < heights[stack[-1]], 处理以stack[-1]对应位置为高度的矩形面积，while 循环直到 条件不满足， 然后i位置入栈
stack = [0, 1, 5, 6]
stack = [0, 1, 2] 处理6，5高度
stack = [0, 1, 2, 3]
stack = [0, 0] 处理3，2，1高度
- 复杂度. 时间：
, 空间:
另一个例子
[2,1,2], ans = 3
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights = [0] + heights + [0]
n = len(heights)
stack = [0]
res = 0
for i in range(n):
if heights[i] >= heights[stack[-1]]:
stack.append(i)
else: # heights[i] < heights[stack[-1]]
while heights[i] < heights[stack[-1]]: # stack 至少含有一个0
idx = stack.pop()
left = stack[-1] + 1 # !!!
res = max(res, (i-left) * heights[idx])
stack.append(i)
return res
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights = [0] + heights + [0]
n = len(heights)
stack = [0]
res = 0
for i in range(1, n):
if heights[i] >= heights[stack[-1]]:
stack.append(i)
else:
while heights[i] < heights[stack[-1]]:
idx = stack.pop()
left = stack[-1] + 1 # !!!
res = max(res, heights[idx]*(i-left))
stack.append(i)
return res
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights = [0] + heights + [0]
n = len(heights)
stack = [0]
res = 0
for i in range(1, n):
height = heights[i]
while stack and height < heights[stack[-1]]:
idx = stack.pop()
left = stack[-1] + 1 # !!! 以heights[idx]为高度的起始点. e.g., [2,1,2]
res = max(res, heights[idx] * (i - left))
stack.append(i)
return res
