【力扣打卡系列】滑动窗口与双指针(接雨水)

坚持按题型打卡&刷&梳理力扣算法题系列，语言为go，Day4

接雨水

• 题目描述
• 解题思路
  • 双指针遍历
  • 前后缀最大值的应用
  • 短板效应，取其中较小的一方即可
  • 计算方式：某一个水桶的接水面积 = 该处pre_max和suf_max小的一方减去高度（height[left] 或 height[right] ）的差值
  • 法二：分别开两个数组pre_max和suf_max，每个位置的接水面积就等于两者中的较小值减去当前位置的height值，遍历累加即可
• 代码参考

func trap(height []int) int {left,right := 0,len(height)-1ans := 0pre_max,suf_max := 0,0for left<=right{pre_max = max(height[left], pre_max)suf_max = max(height[right], suf_max)if pre_max < suf_max{ans += pre_max - height[left]left++}else{ans += suf_max -height[right]right--}}return ans
}

• tips
  • Go 语言的 for 循环支持三种形式：
  • 传统的三部分形式：for init; condition; post { ... }
  • 基于范围的循环：for i := range someSlice { ... }
  • 简单循环条件：for condition { ... }
  • 注意：前缀和跟left，后缀和跟right，不需要单开遍历变量i