心焦U，出三小hrad
心焦U
42. Trapping Rain Water
有n个非负整数，每个整数的宽度是1
请问下雨后积水的面积
思路:
积水的条件是左右边界比中间高
透过一个递减的monotonic stack去存值
递减monotonic stack的特性
当遇到当前值比stack top的值还大的时候
就把top pop出来，一直重复这个动作就可以得到一个递减的排序
知道这个概念后就可以开始解题了
去遍寻heigt阵列，当height[i]>stack的top
就把stack top pop出来，这个pop出来的值会是底部，height[i]就是右边界
再来去检查stack里面还有没有值
1.没有，不会有积水
2.有，左边界为新的stack的top
且积水面积为(右边界-左边界-1)*(min(height[左边界],height[右边界])-height底部])
最后要把height[i] push进stack
重复这些动作就能得到答案了
golang code :
func trap(height []int) int {
stack := []int{}
ans := 0
for i := 0; i < len(height); i++ {
for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
bottomidx := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack) == 0 {
break
}
leftbound := stack[len(stack)-1]
width := i - leftbound - 1
top := min(height[i], height[leftbound])
ans += (top - height[bottomidx]) * width
}
stack = append(stack, i)
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}

超难 我看解答 哭了

心焦u

995