接雨水

Image 56.png
https://mp.weixin.qq.com/s/f9ebzbwymR8jQeUDxjeCDA

暴力

  1. class Solution {
  2.     public int getMax(int[] nums, int l, int r){
  3.         int res = nums[l];
  4.         for(int i = l; i <= r; i++){
  5.             res = Math.max(res, nums[i]);
  6.         }
  7.         return res;
  8.     }
  9.     public int trap(int[] height) {
  10.         int res = 0;
  11.         for(int i = 1; i < height.length - 1; i++){
  12.             int maxL = getMax(height, 0, i - 1);
  13.             int maxR = getMax(height, i + 1, height.length - 1);
  14.             if(maxL > height[i] && maxR > height[i]){
  15.                 res += Math.min(maxL, maxR) - height[i];
  16.             }
  17.         }
  18.         return res;
  19.     }
  20. }

dp记录-左右最大值

  1. class Solution {
  2.     public int trap(int[] height) {
  3.         int n = height.length;
  4.         if(n == 0) return 0;
  5.         //dp[i][0] i左边最大值
  6.         //dp[i][1] i右边最大值
  7.         int[][] dp = new int[n][2];
  8.         dp[0][0] = height[0];
  9.         dp[n - 1][1] = height[n - 1];
  10.         for(int i = 1; i < n; i++){
  11.             dp[i][0] = Math.max(dp[i - 1][0], height[i]);
  12.         }
  13.         for(int i = n - 2; i >= 0; i--){
  14.             dp[i][1] = Math.max(dp[i + 1][1], height[i]);
  15.         }
  16.         int res = 0;
  17.         for(int i = 1; i < n - 1; i++){
  18.             res += Math.min(dp[i][0], dp[i][1]) - height[i];
  19.         }
  20.         return res;
  21.     }
  22. }

双指针

  1. class Solution {
  2.     public int trap(int[] height) {
  3.         int res = 0;
  4.         int l = 0, r = height.length - 1;
  5.         int lmax = 0, rmax = 0;
  6.         while(l <= r){
  7.             if(lmax <= rmax){
  8.                 lmax = Math.max(lmax, height[l]);
  9.                 res += lmax - height[l++];
  10.             }else{
  11.                 rmax = Math.max(rmax, height[r]);
  12.                 res += rmax - height[r--];
  13.             }
  14.         }
  15.         return res;
  16.     }
  17. }

单调栈

这道题目可以用单调栈来做。单调栈就是比普通的栈多一个性质，即维护栈内元素单调。
比如当前某个单调递减的栈的元素从栈底到栈顶分别是：[10, 9, 8, 3, 2]，如果要入栈元素5，需要把栈顶元素pop出去，直到满足单调递减为止，即先变成[10, 9, 8]，再入栈5，就是[10, 9, 8, 5]。