今日专题：单调栈进阶
今日总结：单调栈的代码写起来感觉还是有点难度，这两道题的解题思路也得好好想一想
42. 接雨水
解法一 ：双指针法
class Solution:
def trap(self, height: List[int]) -> int:
#按列计算当前列上可以接多少水，当前列左侧最高和右侧最高取最小值
size=len(height)
left=[0]*size
right=[0]*size
res=0
for i in range(1,size):
left[i]=max(left[i-1],height[i-1])
right[size-1-i]=max(right[size-i],height[size-i])
print(left)
print(right)
for j in range(size):
res+=max(0,min(left[j],right[j])-height[j])
return res
解法二：单调栈法
class Solution:
def trap(self, height: List[int]) -> int:
res=0
size= len(height)
if size<2:
return res
st=[0]
for i in range(1,size):
if height[i]<height[st[-1]]:
st.append(i)
elif height[i]==height[st[-1]]:
st.pop()
st.append(i)
else:
while len(st)>0 and height[i]>height[st[-1]]:
j=st.pop()
if len(st)>0:
res+=(min(height[i],height[st[-1]])-height[j])*(i-st[-1]-1)
st.append(i)
return res
84. 柱状图中最大的矩形
思路：遍历每一根柱子，找到左右两侧比其小的第一根，可形成矩阵大小为h[i]*(m-n)
总结：在原数组开头和结尾均加上0值
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
#遍历每一根柱子，找到左右两侧比其小的第一根，可形成矩阵大小为h[i]*(m-n)
res=0
st=[]
heights=[0]+heights+[0]
size=len(heights)
for m in range(size):
if len(st)==0:
st.append(heights[m])
continue
while len(st)>0 and heights[m]<heights[st[-1]]:
i=st.pop()
res=max(res,heights[i]*(m-st[-1]-1))
st.append(m)
return res
