return dist

用线性的时间复杂度找左右两侧第一个大于/小于当前元素的位置。

classSolution:

deflargestRectangleArea(self,heights) ->int:

heights.append(0)

stack= [-1]

result=0

for iinrange(len(heights)):

while stackand heights[i]< heights[stack[-1]]:

cur= stack.pop()

result=max(result, heights[cur]* (i- stack[-1]-1))

stack.append(i)

return result

classSolution:

deftrap(self,height: List[int]) ->int:

stack= []

result=0

for iinrange(len(height)):

while stackand height[i]> height[stack[-1]]:

cur= stack.pop()

ifnot stack:

result+= (min(height[stack[-1]], height[i])- height[cur])* (i- stack[-1]-1)

stack.append(i)

return result

单调栈的拓展，可以以线性时间获得区间最大/最小值。