LeetCode220806_72、接雨水

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

示例 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/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解 接到的雨水总和为各个元素对应的坑洼地带之和(元素的左边最高和右边最高形成壁垒，元素对应高度与边界较低高度的差是接水坑洼)

题解一、在循环中找到各个元素的左右壁垒（元素的左右最高边界），并且进行雨水求和。

class Solution{public int trap(int[] height){int sum = 0;for(int i = 1; i < height.length - 1; i++){int leftMax = 0;for(int j = i - 1; j >= 0; j--){leftMax = Math.max(leftMax, height[j]);}int rightMax = 0;for(int j = i + 1; j < height.length; j++){rightMax = Math.max(rightMax, height[j]);}int min = Math.min(leftMax, rightMax);if(min > height[i]){sum += (min - height[i]);}}return sum;}
}

题解二、每次循环都需要从元素遍历到左右边界(索引0，height.length - 1)寻找左右最大最小，可直接根据当前元素的左边元素的值和左边元素的最大左边界的值进行比较，获取，即maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1])；右边同理。

class Solution{public int trap(int[] height){int sum = 0;int[] maxLeft = new int[height.length];int[] maxRight = new int[height.length];for(int i = 1; i < height.length - 1; i++){maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1]);}for(int j = height.length - 2; j >= 1; j--){maxRight[j] = Math.max(maxRight[j + 1], height[j + 1]);}for(int m = 1; m < height.length - 1; m++){int min = Math.min(maxLeft[m], maxRight[m]);if(min > height[m]){sum += min - height[m];}}return sum;}
}

题解三、每次元素求接住的雨水量只需记录当前元素的左边界，之前元素的左边界无需占用空间，右边同理，使用双指针，进行左右边界的灵活记录，并且对于左边位置的元素而言，当左边界小于右边界时，元素可接的雨水量由左边界确定，右边同理。

class Solution{public int trap(int[] height){int leftMax = 0;int rightMax = 0;int left = 0;int right = height.length - 1;int sum = 0;while(left <= right){if(leftMax < rightMax){sum += Math.max(0, leftMax - height[left]);leftMax = Math.max(leftMax, height[left]);left++;}else{sum += Math.max(0, rightMax - height[right]);rightMax = Math.max(rightMax, height[right]);right--;}}return sum;}
}

题解四、单调栈，解决。

class Solution{public int trap(int[] height){Deque stack = new ArrayDeque<>();int len = height.length;int res = 0;for(int i = 0; i < len; i++){while(!stack.isEmpty() && height[i] > height[stack.peek()]){int top = stack.pop();if(stack.isEmpty()){break;}int left = stack.peek();int curWidth= i - left - 1;int curHeight = Math.min(height[left], height[i]) - height[top];res += curWidth * curHeight;}stack.push(i);}return res;}
}

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