解法: 雨水面积 = 底边长w*雨水高度h
双指针:
动态规划:
单调栈:
- //双指针法:寻找每个位置上的可堆积的雨水高度,即左右寻找水桶的最高边界,取最低值-底部高度
- class Solution {
- public int trap(int[] height) {
- int sum= 0;
- //计算每一个位置可堆积的雨水高度,叠加
- int lheight, rheight;
- for(int i = 0; i < height.length; i++){
- lheight = 0;
- rheight = 0;
- for(int l = i-1; l >= 0; l--){
- lheight = Math.max(lheight,height[l]);
- }
- for(int r = i+1; r < height.length; r++){
- rheight = Math.max(rheight,height[r]);
- }
- int get = Math.min(lheight,rheight)-height[i];
- sum += get>0? get:0;
- }
- return sum;
- }
- }
-
-
- //动态规划:最快,按列计算存水量
- class Solution {
- public int trap(int[] height) {
- int len = height.length;
- int[][] dp = new int[len+2][2];//初始值全为0,首尾添加虚拟节点可存水高度一定为0
- int sum= 0;
- for(int left = 1; left <= len; left++){
- dp[left][0] = Math.max(dp[left-1][0],height[left-1]);//左侧高度
- int right = len+2-1-left;
- dp[right][1] = Math.max(dp[right+1][1],height[right-1]);//右侧高度
- }
- for(int i = 1; i <= len; i++){
- int get = Math.min(dp[i][0],dp[i][1])-height[i-1];
- sum += get>0?get:0;
- }
- return sum;
- }
- }
-
- //单调栈:按行计算存水量
- class Solution {
- public int trap(int[] height) {
- Stack<Integer> index = new Stack<>();
- int sum = 0;
- index.push(0);
- for(int i = 1; i < height.length; i++){
- int cur = index.peek();
- while(!index.isEmpty() && height[i] >= height[cur]){
- cur = index.pop();
- if(!index.isEmpty()){
- int pre = index.peek();
- sum += (i-pre-1)*(Math.min(height[i],height[pre])-height[cur]);
- cur = pre;
- }
- }
- index.push(i);
- }
- return sum;
- }
- }