厦门网站建设68,网站下载免费,重庆哪里好玩,建筑劳务公司名字起名大全这是一道 困难 题
题目来自#xff1a; https://leetcode.cn/problems/trapping-rain-water/
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
示例 1#xff1a; 输入#xff1a;height [0,…这是一道 困难 题
题目来自 https://leetcode.cn/problems/trapping-rain-water/
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
示例 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 个单位的雨水蓝色部分表示雨水。 示例 2
输入height [4,2,0,3,2,5]
输出9 提示
nheight.lengthn height.lengthnheight.length1n2∗1041 n 2 * 10^41n2∗1040height[i]1050 height[i] 10^50height[i]105
解题思路
使用单调栈的思路假如给定的每个柱子是逐个变矮的那么可以接的雨水就是0。 如果这时候突然来了一个变高的柱子 4 那么这个柱子就会使得当前柱状图可以接雨水了。 如上图所示
先将栈顶的柱子取出柱子3使用其左边柱子的高度和新增柱子高度的最小值 - 其本身高度* 其宽度得出当前柱子的接水量累加到答案中。注意如果栈中目前只有一个柱子的话其左边高度设为0即不可以接水。这时如果新的栈顶柱子柱子2依然比新增的柱子矮继续取出栈顶柱子并计算其接水量注意这是宽度应该是柱子3的宽度 柱子2的宽度。这时栈顶柱子1的高度 大于 新增的柱子4 的高度柱子4入栈注意这时柱子4的宽度 柱子2 柱子3 柱子4 的总宽度即前面所有出栈的柱子的宽度都需要保留下来因为如果再来一个第5个柱子的高度 柱子4的高度的话前面那么宽度还是有用的。
代码实现
Java 代码实现
class Solution {private Dequeint[] stack new LinkedList();public int trap(int[] height) {int n height.length ;if(n 1){return 0;}int ans 0;for(int h : height){int w 0;while(!stack.isEmpty() h stack.peek()[1]){int[] top stack.pop();w top[0];if(!stack.isEmpty()){ans w * (Math.min(stack.peek()[1], h) - top[1]);}}stack.push(new int[]{w 1, h});}return ans;}
}Go 代码实现
func trap(height []int) int {n : len(height)if n 1 {return 0}stack : [][]int{}ans : 0for _, h : range height {if len(stack) 0 {stack append(stack, []int{1, h})continue}w : 0for len(stack) 0 h stack[len(stack) - 1][1] {top : stack[len(stack) - 1]stack stack[:len(stack) - 1]w top[0]if len(stack) 0 {ans w * (min(stack[len(stack) - 1][1], h) - top[1])}}stack append(stack, []int{w 1, h})}return ans
}func min(a int, b int) int {if a b {return b}return a
}复杂度分析
时间复杂度O(n)O(n)O(n)
空间复杂度O(n)O(n)O(n)
