网站建设方案申请,做淘宝导航网站,wordpress怎么去除底部,网站制作需要平台题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
示例 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出#xff1a;6 解释#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高…题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
示例 输入height [0,1,0,2,1,0,1,3,2,1,2,1] 输出6 解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。
解析
这道题可以有暴力法、动态规划法、单调栈法、双指针法等由于上一道题是用的双指针为了好记这里也使用双指针法。 先贴一个讲的比较好的视频视频讲解 这道题使用双指针主要的思路是比如上图中的最高的那块木板左边的位置能解多少雨水取决于它左边木板的最大高度因为低于这个最大高度是会漏出去的。 基础版的双指针需要两个额外的数组一个存从左边开始到i的最大高度一个存从右边开始的。计算的方法就是比较前一时刻的最大值和此刻的比较然后取max。这个时候就有了两个数组取min后和本身的数组比较就是能接的最大容量
func trap(height []int) (ans int) {n : len(height)preMax : make([]int, n) // preMax[i] 表示从 height[0] 到 height[i] 的最大值preMax[0] height[0]for i : 1; i n; i {preMax[i] max(preMax[i-1], height[i])}sufMax : make([]int, n) // sufMax[i] 表示从 height[i] 到 height[n-1] 的最大值sufMax[n-1] height[n-1]for i : n - 2; i 0; i-- {sufMax[i] max(sufMax[i1], height[i])}for i, h : range height {ans min(preMax[i], sufMax[i]) - h // 累加每个水桶能接多少水}return
}func min(a, b int) int { if a b { return b }; return a }
func max(a, b int) int { if a b { return b }; return a }如果不想开辟两个新组数那么就使用两个单纯的指针分别从左右开始遍历那么此刻我们知道比如左右都遍历了两个位置那么中间位置的容量我们是不知道的但是如果前缀最大值比后缀最大值小那么左边木桶的容量就是前缀最大值的容量算完后向右扩展同理如果后缀最大值比前缀最大值小那么右边这个木桶的容量就是后缀最大值的容量。。。
func trap(height []int) int {n : len(height)ans : 0left : 0right : n-1preMax : 0sufMax : 0for left right {preMax max(preMax, height[left])sufMax max(sufMax, height[right])if preMax sufMax {ans preMax - height[left]left} else {ans sufMax - height[right]right--}}return ans
}func max(a, b int) int{if a b {return a}return b
}
