Leetcode【数组/栈/动态规划/双指针】 | 42.Trapping Rain Water 接雨水问题

Leetcode | 42.Trapping Rain Water 接雨水

• 题目
• 解题
• • 暴力解法
  • • 思路
    • 代码
  • 动态规划（对暴力解法的改进）
  • • 思路
    • 代码
  • 双指针
  • • 思路
    • 代码
  • 单调栈
  • • 思路
    • 代码

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water

解题

 将该题分解为如下问题：一列一列的计算，对每一列来说，第i列所能接的雨水高度是它左边最高的和右边最高的之中矮的那方减去它本身的高度，即min(left_max[i], right_max[i]) - height[i]（注意前提：min(left_max[i], right_max[i]) 要比height[i]大）

暴力解法

思路

 直接一列一列计算，枚举每一列，分别从左到右遍历一遍求出左边最大和右边最大，然后将每列能承载的雨水计算出来累加。
　因为要遍历两遍，所以时间复杂度为O(n²), 空间复杂度为O(1)。

代码

class Solution {public int trap(int[] height) {//暴力解法int n = height.length;int res = 0;//遍历每一列for(int i = 1; i < n; i++){int left_max=0 ,right_max = 0;//求出该列左边最高 和 右边最高//求左边最高，从左往右遍历到当前列(注意：比较一定要包含当前列)for(int j = 0; j <= i; j++){left_max = Math.max(left_max, height[j]);}//求右边最高，从右往左遍历到当前列for(int j = n-1;j >= i; j--){right_max = Math.max(right_max,height[j]);}//计算当前列可积雨水量并累加res += Math.min(left_max,right_max) - height[i];}return res;}
}

动态规划（对暴力解法的改进）

思路

对每一列的left_max和right_max的求解进行改进，不用每次都要重复遍历一遍整个数组,用数组将每次求解的left_max和right_max保存下来。
第一种方法（使用一维数组）：
从左到右遍历一遍数组求第i列左边的最高dp_leftmax[i] = max(dp_leftmax[i-1]，height[i-1]
从右到左遍历一遍数组求第i列右边的最高dp_rightmax[i] = max(dp_rightmax[i+1]，height[i+1]
第二种方法（使用二维数组）：
创建一个二维数组dp[i][j] (i = 0~n-1; j = 1/0)
第i列左边最高: dp[i][0]= max(dp[i-1][0], height[i-1])
第i列右边最高: dp[i][1]= max(dp[i+1]

时间复杂度：O(n)
空间复杂度：O(n)

代码

 动态规划之一维数组，求左/右边最高时不包括当前列，将前提放在最后判断。

class Solution {public int trap(int[] height) {//动态规划 一维数组int n = height.length;int res = 0;//定义一维数组存储每列的左/右边最高int[] dp_leftmax = new int[n];int[] dp_rightmax = new int[n];//求每列的左边最高，从左到右遍历for(int i = 1; i < n-1; i++){dp_leftmax[i] = Math.max(dp_leftmax[i-1],height[i-1]);}//求每列的右边最高，从右到左遍历for(int i = n-2; i >= 0; i--){dp_rightmax[i] = Math.max(dp_rightmax[i+1],height[i+1]);}//遍历每一列,求出每列可积雨水量并累加for(int i = 1; i < n-1; i++){//因为前面求左右边最高时没有将当前列比较进去，所以这里要判断前提int min = Math.min(dp_leftmax[i],dp_rightmax[i]);if(min > height[i]){res += min - height[i];}}return res;}
}

 动态规划一维数组，求左/右边最高时包括当前列高度，直接在这之中将前提判断出来。不用最后判断，但是需要额外初始化第一列和最后一列的值，并且判断空数组时的情况。

class Solution {public int trap(int[] height) {//动态规划之一维数组int n = height.length;int res = 0;//要记得判断特殊情况if(n == 0){return 0;}//定义一维数组存储每列的左/右边最高int[] dp_leftmax = new int[n];int[] dp_rightmax = new int[n];//初始化第一列和最后一列dp_leftmax[0] = height[0];dp_rightmax[n-1] = height[n-1];//求每列的左边最高，从左到右遍历for(int i = 1; i < n-1; i++){dp_leftmax[i] = Math.max(dp_leftmax[i-1],height[i]);}//求每列的右边最高，从右到左遍历for(int i = n-2; i >= 0; i--){dp_rightmax[i] = Math.max(dp_rightmax[i+1],height[i]);}//遍历每一列,求出每列可积雨水量并累加for(int i = 1; i < n-1; i++){int min = Math.min(dp_leftmax[i],dp_rightmax[i]);res += min - height[i];    }return res;}
}

 动态规划之二维数组

class Solution {public int trap(int[] height) {//动态规划int n = height.length;int res = 0;//定义二维数组存储每列的左/右边最高int[][] dp = new int[n][2];//求每列的左边最高，从左到右遍历for(int i = 1; i < n-1; i++){dp[i][0] = Math.max(dp[i-1][0] ,height[i-1]);}//求每列的右边最高，从右到左遍历for(int i = n-2; i >= 0; i--){dp[i][1] = Math.max(dp[i+1][1],height[i+1]);}//遍历每一列,求出每列可积雨水量并累加for(int i = 1; i < n-1; i++){int min = Math.min(dp[i][0],dp[i][1]);if(min > height[i]){res += min - height[i];}}return res;}
}

双指针

思路

 同样是对每一列的左/右边最高left_max和right_max的求解进行改进。不需要额外创建新数组，用变量left_max和right_max来存储。但是这两个变量还是通过left和right两个指针从两端开始遍历，依次递推得到的。
只需遍历一遍，时间复杂度仍为O(n); 但不许额外创建数组，空间复杂度优化为O(1)。

代码

class Solution {public int trap(int[] height) {//双指针改进int sum = 0;int left_max = 0;int right_max = 0;int left = 1;int right = height.length - 2;for(int i = 1; i < height.length -1;i++){//或者用while循环//while(left <= right)//左边比右边更小时，从左到右更，使用左边最高if (height[left-1] < height[right+1]){left_max = Math.max(left_max,height[left-1]);int min = left_max;if(min > height[left]){sum = sum + (min-height[left]);}left++;}else{            //右边比左边更小时，从右到左更，使用右边最高right_max = Math.max(right_max,height[right+1]);int min = right_max;if(min>height[right]){sum = sum+(min-height[right]);}right--;}}return sum;}
}

单调栈

 此解法转载自 甜姨的接雨水问题详解，详见上述链接。这个里面也有以上几种解法，这篇博客只做自己的整理。
 该题是典型的单调栈问题，单调栈：就是要维护栈内元素保持单调顺序的栈。比如当某个单调递减的栈的元素从栈底到栈顶是：[9,8,7,3,2], 如果要入栈元素5，需要把栈顶元素pop出去，直到满足单调递减为止，即先变成[9,8,7]，再入栈5，最终变为[9,8,7,5]。
　如果说之前的解法是按竖着一列一列的雨水来计算的，单调栈是按一行一行的雨水来计算的。如下图源自 甜姨的接雨水问题详解）。
　

思路

 按列枚举，将每一列的索引 i 依次入栈，保持每列的高度height[i]单调递减。[注：栈内元素的值为索引。以下称栈顶元素指栈顶元素所对应的列的高度]
　满足接雨水的条件是形成凹槽:
　1、如果当前列的高度<=栈顶元素的高度，直接入栈，栈里还是保持单调递减，说明此时还形不成凹槽；
　2、当遍历到当前列的高度>栈顶元素时，此时形成了凹槽，将栈中小于当前列高度的元素pop出来，将此时凹槽的大小计算出来进行累加。
　　 pop一个栈顶元素（比较一次当前列高度与栈顶元素的大小），要计算一次凹槽大小，其实计算的就是pop出的那个栈顶元素所在列(当前栈顶元素)到当前列之间的还未计算的凹槽大小。当前凹槽大小 = 高度 * 宽度。
　　 高度 = 当前栈顶元素与当前列之间的最低高度 - 还未计算的最低高度（还未计算的最低高度就是遍历到当前列之前的栈顶元素。）
　　 宽度 = 当前列 与 当前栈顶元素所在列之间的距离= 当前列 - 当前栈顶元素 -1
　　 由于每列最多入栈出栈一次，所以时间复杂度为O(n)。

代码

class Solution {public int trap(int[] height) {//定义一个栈Stack<Integer> stack = new Stack<>();int n = height.length;int res = 0;//存结果//遍历每一列for(int i = 0; i < n; i++){//当前列高度比栈顶大的时候，形成凹槽,计算凹槽大小while(!stack.isEmpty() && height[stack.peek()] < height[i]){int bottom_index = stack.pop();//当前栈顶元素为当前栈内最小值，即在遍历到这列之前还未计算的最低的行。//当前列和栈顶元素相等时，只保留最右边即最新入栈的元素，其他的都popwhile(!stack.isEmpty() && height[stack.peek()] == height[bottom_index]){stack.pop();}//避免特殊情况if(!stack.isEmpty()){//计算当前凹槽并类加：（当前栈顶元素与当前列之间的最低高度 - 还未计算的最低高度）*（当前列 - 当前栈顶元素）res += (Math.min(height[i],height[stack.peek()])-height[bottom_index])*(i-stack.peek()-1);}}//其余情况：当前列高度比栈顶小或相等的话，直接入栈，栈内保持单调stack.push(i);}return res;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！