leetcode42，接雨水，思路清晰，由简入繁讲解，java语言
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode42，接雨水，思路清晰，由简入繁讲解，java语言，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5379字，纯文字阅读大概需要8分钟。
内容图文
记录自己刷题弄的一些思路
先列出问题
给定 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 个单位的雨水（蓝色部分表示雨水）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题只要有4个解法，分别是暴力解，动态规划，双指针（面试官比较想看到的答案），以及栈（单调递减栈）。
首先必须会暴力解，很多人直接一上来就想双指针，动态规划等等，只能说除非你做了很多类似的题，一看就能想到的话，不然你很难想出最优解。
这道题先用暴力解解出来，后来才发现暴力解有很多重复操作，因此可以用动态规划来记录一些以前操作的解，这就是一个思路的提升。再到双指针其实是动态规范的一种更好的优化。最后一种解法单调递减栈是比较有意思的解法。
（提示：从暴力解–动态规划–双指针都是垂直方向积水的计算）
1.暴力解
从左到右遍历数组，每一个位置 i 能否积水（或者说积水多少）取决于其左边最大的边界和其右边最大边界来决定的，当左边最大边界及右边最大边界决定后，根据木桶原理，左右边界最小值按理应该是该位置能积水多少，但是别忘了还得减去该位置的高度，因为假如左右边界最小值是2，但是该柱子的高度也是2，就没法积水。
public int trap(int[] height) {
if(height.length <=2) {
return 0;
}
int left_max;
int right_max;
int sum = 0;
for(int i=1;i<height.length;i++){
left_max = height[i];
right_max = height[i];
for(int j=i-1;j>=0;j--){
left_max = Math.max(height[j],left_max);
}
for(int j=i+1;j<height.length;j++){
right_max = Math.max(height[j],right_max);
}
sum += Math.min(left_max,right_max) - height[i];
}
return sum;
}
时间复杂度O(n^2)
空间复杂度O(1)
2.动态规划
理解了上述暴力解那就很容易地想到，每一步都要去找其左右边界最大值是一个重复过程，例如某个位置 i ，其左边边界最大值无非就是 i-1 位置左边边界的最大值 和 i 处高度的相比，即得出下面状态转移过程（使用动态规划，只要有状态转移方程那就很简单写出相应语言解法）
Left_max[i] = Max( Left_max[i-1] ， heigth[i] )
同理右边边界最大值状态转移方程
Right_max[j] = Max( Right_max[j+1] ， heigth[j] )
使用两个数组来充当备忘录。
public int trap(int[] height) {
if(height.length <=2) {
return 0;
}
int size = height.length;
int[] left_max_arr = new int[size];
int[] right_max_arr = new int[size];
int sum = 0;
left_max_arr[0] = height[0];//初始条件
for(int i=1;i<size;i++){
left_max_arr[i] = Math.max(left_max_arr[i-1], height[i]);
}
right_max_arr[size-1] = height[size-1];//初始条件
for(int i=size-2;i>=0;i--){
right_max_arr[i] = Math.max(right_max_arr[i+1], height[i]);
}
for(int i=0;i<size;i++){
sum += Math.min(left_max_arr[i], right_max_arr[i]) - height[i];
}
return sum;
}
时间复杂度O(n)
空间复杂度O(n)
3.双指针方法(最优解)
从动态规划解法可以看出只要当left_max_arr[i] < right_max_arr[i]（木桶原理），该 i 位置积水量是由left_max_arr[i]决定的，反过来当left_max_arr[i] > right_max_arr[i]（木桶原理），该 i 位置积水量是由right_max_arr[i]决定的。
因此都不需要两个数组来记录左边最大边界和右边最大边界，只需要两个指针指向数组的left端和right端，同时两个变量记录left_max，和right_max。左右指针移动的规则是当height[left] < height[right]，积水量看left_max，并且左指针left往right移动。
或许读者会问，为什么是这样的移动的规则呢？想一想，前面说的当left_max_arr[i] < right_max_arr[i]（木桶原理），该 i 位置积水量是由left_max_arr[i]决定。那么当height[left] < height[right]，left_max_arr[left] 必然小于right_max_arr[left] ，因为right_max_arr[left] >= right_max_arr[right] >= height[right]；
这里比较绕，重新再打一次数学表达式来表示
（
动态规划解法可以看出当left_max_arr[i] < right_max_arr[i]（木桶原理），该 i 位置积水量是由left_max_arr[i]决定的，所以下面的各种思路都是为了得到当height[left] < height[right]，left_max_arr[left] <= right_max_arr[left]，移动左指针就好；
当height[left] < height[right]时：
left_max_arr[left] = Max(left_max_arr[left-1]，height[left])；
而right_max_arr[left] = Max(right_max_arr[left+1]，height[left]));
因此left<right时，right_max_arr[left] > right_max_arr[right]
而right_max_arr[right] =Max(right_max_arr[right+1]，height[right])) ，并且height[right] > height[left] ;
right_max_arr[left] > right_max_arr[right] >= height[right] > height[left]
因为left，right一开始从左右两端往之间靠，上一次的移动也是采用该规则，就有必然有
left_max_arr[left] <= right_max_arr[left]；）
public int trap(int[] height) {
if(height.length <=2) {
return 0;
}
int left = 0;
int right = height.length-1;
int left_max = 0;
int right_max = 0;
int sum = 0;
while(left<right){
if(height[left] < height[right]){
left_max = Math.max(left_max,height[left]);
sum += left_max - height[left];
left++;
} else {
right_max = Math.max(right_max,height[right]);
sum += right_max - height[right];
right--;
}
}
return sum;
}
时间复杂度O(n)
空间复杂度O(1)
4.栈思想
上面的思路都是基于垂直的积水，即每个位置 i 的积水 = “某个计算的高度” - 该位置柱子的高度；其实也可以基于横向的计算积水，积水总量 = ∑ （左右边界积水高度极小值 *边界的距离）。这个直接上代码才能说得通
public int trap(int[] height) {
if(height.length <=2) {
return 0;
}
Stack<Integer> stack = new Stack<Integer>();
int sum = 0;
for(int i=0;i<height.length;i++){
//产生积水的位置是低洼处，也就是此位置的高度比前一个位置高度要大
while(!stack.isEmpty() && height[stack.peek()] <= height[i]){
int lastIndex = stack.pop();
if(!stack.isEmpty()){
//横向积水高度
int hei = Math.min(height[stack.peek()],height[i]) - height[lastIndex];
//横向积水宽度
int distance = i - stack.peek() - 1;
sum += (distance*hei);
}
}
stack.push(i);
}
return sum;
}
内容总结
以上是互联网集市为您收集整理的leetcode42，接雨水，思路清晰，由简入繁讲解，java语言全部内容，希望文章能够帮你解决leetcode42，接雨水，思路清晰，由简入繁讲解，java语言所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。