|
单调栈法：
单调栈解法是按照行来计算的。对应在图中的中间倒坦克部分，就是先算坦克尖的面积，再算坦克身的面积。
比较难理解，会就会吧，不会就看动归。
首先维持单调栈一贯的风格，stack储存下标，sum用来计数。然后遍历，单调栈的元素顺序从栈头到栈尾是从小到大，如果一旦发现待添加的柱子高度大于栈头元素，说明出现凹槽，从栈头开始数，第二个元素代表的就是凹槽左边的柱子，待添加的元素就是右边的柱子。
当遇到相同高度的柱子的时候，我们要更新stack让旧元素弹出，放入新的元素，因为我们是从左向右遍历，所以在计算宽度的时候我们要用右边的那个柱子来限定宽度。
class Solution:
def trap(self, height: List[int]) -> int:
if len(height)<2:#剪枝
return 0
stack=[0]
sum=0
for i in range(1,len(height)):
if height[i]<height[stack[-1]]:
stack.append(i)
if height[i]==height[stack[-1]]:
stack.pop()
stack.append(i)
else:
while stack and height[i]>height[stack[-1]]:
mid=stack.pop()
if stack:
h=min(height[stack[-1]],height[i])-height[mid]
w=i-stack[-1]-1
sum+=w*h
stack.append(i)
return sum
'''
'''
动态规划法：
经典动归解法。每一个地方能接的雨水，主要取决于：这个位置左边最高的柱子和右边最高的柱子这两个柱子之中较小的那一个决定，即短板效应。
所以我们如果想统计出每一个地方能接的雨水是多少，首先要做的准备工作就是，把这个位置左右两边最高的柱子统计出来，这需要两个数组分别进行统计。统计左max的时候正向遍历，统计右max的时候，反向遍历。
并且要注意，遍历最开始的那个元素是直接等于height里面对应下标元素的，否则我们无法开始统计。
当一切准备工作就绪，我们开始进入动态规划，选取两个柱子之间较小的一个，然后拿它减去当前柱子高度，就是当前位置能收集到的雨水。当然这个值要＞0才可以随着遍历累加
class Solution:
def trap(self, height: List[int]) -> int:
if len(height)<2:#剪枝
return 0
maxleft=[0]*len(height)
maxright=[0]*len(height)
maxleft[0]=height[0]
for i in range(1,len(height)):
maxleft[i]=max(height[i],maxleft[i-1])
maxright[len(height)-1]=height[len(height)-1]
for i in range(len(height)-2,-1,-1):
maxright[i]=max(height[i],maxright[i+1])
sum=0
for i in range(1,len(height)):#动态规划正式开始
count=min(maxleft[i],maxright[i])-height[i]
if count>0:
sum+=count
return sum
''''''
|