def largestRectangleArea2(self, heights) -> int:
"""
暴力法 O(N^2), 以 heights[i] 的高度为高，求左右满足的宽
"""
lg = len(heights)
maxx = 0
for i in range(lg):
tmp = heights[i]
left, right = i, i
while left > 0 and heights[left - 1] >= heights[i]:
left -= 1
while right < lg - 1 and heights[right + 1] >= heights[i]:
right += 1
maxx = max(tmp * (right - left + 1), maxx)
return maxx
def largestRectangleArea(heights) -> int:
"""
单调栈, stack 递增
cur 比 stack[-1]大，入栈;
cur 比 stack[-1]小，依次出栈至 stack[-1]小于cur
以出栈元素的值为高，求宽，更新最值
"""
heights.append(0) # 判断最后一个元素为高的情况
lg = len(heights)
stack = [0]
maxx = 0
for i in range(1, lg):
if not stack&nbs***bsp;heights[stack[-1]] <= heights[i]:
stack.append(i)
else:
while stack and heights[stack[-1]] >= heights[i]:
h = heights[stack[-1]]
stack.pop()
# stack 为空，说明当前height[i] 小于 i之前所有的值
w = i if not stack else i - (stack[-1] + 1)
maxx = max(maxx, h*w)
stack.append(i)
return maxx
# i=3 结束时，stack = [0,3]；i=4, height[4]=0时，w = i - (0 + 1) = 3
heights = [0,1,2,1]
print(largestRectangleArea(heights))
投递拼多多等公司10个岗位 >