【动态规划专题】LeetCode 42. 接雨水

共以下 8 个回答

• 超人阿光 永久会员 2024年12月10日 下午7:01

  class Solution {
  public int trap(int[] height) {
  int n = height.length;
  if(n 0 || n 1) return 0;

      int[] dpl = new int[n]; // 柱子i左边最高柱子高度
      dpl[0] = height[0];
      for(int i = 1 ; i < n ; i++){
          dpl[i] = Math.max(dpl[i-1] , height[i]);
      }
  
      int[] dpr = new int[n]; // 柱子i右边最高柱子高度
      dpr[n-1] = height[n-1];
      for(int i = n-2 ; i >= 0 ; i--){
          dpr[i] = Math.max(dpr[i+1] , height[i]);
      }
  
      int res = 0 ; 
      for(int i = 0 ; i < n ; i++){
          res += (Math.min(dpl[i] , dpr[i]) - height[i]); // 累加每根柱子储水量
      }
      return res;
  }
  

  }

  1 赞同 0 条回复

  登录以回复
• 云无深雁影 普通 2024年4月10日 下午11:21

  class Solution {
  public int trap(int[] height) {
  int[] water = new int[height.length];
  int i = 0;
  int ans = 0;
  while(i < height.length){
  int curentHeight = height[i];
  int j = i + 1;
  while(j < height.length){
  if(height[j] < height[i])
  j++;
  else
  break;
  }
  if(j < height.length){
  for(int k = i + 1; k < j; k++ )
  water[k] = height[i];
  }
  i = j ;
  }
  i = height.length – 1;
  while(i >= 0){
  int j = i – 1;
  while(j >= 0){
  if(height[j] < height[i])
  j–;
  else
  break;
  }
  if(j >= 0 ){
  for(int k = i – 1; k > j; k– )
  water[k] = height[i];
  }
  i = j ;
  }
  for(int h = 0; h < height.length; h++)
  ans += Math.max(water[h] – height[h],0);
  return ans;
  }
  }
  //来回两次遍历 时间复杂度On 空间复杂度On

  class Solution {
  public int trap(int[] height) {
  int ans = 0;
  int i = 0;
  int leftMax = height[i];
  int j = height.length – 1;
  int rightMax = height[j];
  while(i < j){
  if(height[i] < height[j]){
  ans += leftMax – height[i];
  i++;
  leftMax = Math.max(leftMax,height[i]);
  }
  else{
  ans += rightMax – height[j];
  j–;
  rightMax = Math.max(rightMax,height[j]);
  }
  }
  return ans;
  }
  }//优化法 空间复杂度降到O1

  0 赞同 0 条回复

  登录以回复
• 方铎码农 普通 2024年4月8日 下午10:29

  class Solution {
  
      // 动态规划法，求左边最高的墙和右边最高的墙
      public int trap(int[] height) {
          int sum = 0;
          int[] max_left = new int[height.length];
          int[] max_right = new int[height.length];
  
          for (int i = 1; i < height.length - 1; i++){
              max_left[i] = Math.max(max_left[i-1],height[i-1]);
          }
          for (int i = height.length - 2; i >= 0; i--){
              max_right[i] = Math.max(max_right[i+1],height[i+1]);
          }
  
          for(int i = 1; i < height.length - 1; i++){
              int min = Math.min(max_left[i],max_right[i]);
              if(min > height[i]){
                  sum += min - height[i];
              }
          }
  
          return sum;
      }
  }
  

  想起来很困难但实现起来很容易的解法，时间复杂度$O(n)$，空间复杂度$O(n)$

  0 赞同 0 条回复

  登录以回复
• 王位詮釋 普通 2024年4月7日 下午8:37

  暴力解法思路：这个题不能把某一位置的水柱与周围位置的水柱混在一起，我们只需要知道某一位置的水柱，然后把所有位置的水柱加一起就可以得出答案。
  而某一位置能存多少水与这个位置两边的最高柱状图有关，所以可以每到一个位置的时候找到这个位置两端的最高的柱状图的值l_max和r_max，然后就可以知道某一位置的水柱值。
  

  备忘录优化：
  class Solution {
      public int trap(int[] height) {
          if(height.length<=0){
              return 0;
          }
          int n = height.length;
          int res = 0;
          int[] l_max = new int[n];
          int[] r_max = new int[n];
          l_max[0] = height[0];
          r_max[n-1] = height[n-1];
          for(int i=1;i<n;i++){
              l_max[i] = Math.max(l_max[i-1],height[i]);
          }
          for(int i=n-2;i>=0;i--){
              r_max[i] = Math.max(r_max[i+1],height[i]);
          }
          for(int i=1;i<n-1;i++){
              res+=Math.min(l_max[i],r_max[i])-height[i];
          }
          return res;
      }
  }
  暴力法每到一个位置的时候都需要来计算左右两边的值，所以我们可以提前把l_max和r_amx计算出来并记录在“备忘录”中，用到的时候直接取就行。
  时间复杂度：O(n)
  空间复杂度：O(n)
  

  双指针优化：
  class Solution {
      public int trap(int[] height) {
          int n = height.length;
          int l_max = 0;//代表左边最高的水柱
          int r_max = 0;//代表右边最高的水柱
          int left = 0;
          int right = n-1;
          int res = 0;
          while(left<right){
              l_max = Math.max(l_max,height[left]);
              r_max = Math.max(r_max,height[right]);
              if(l_max < r_max){
                  res+=l_max-height[left];
                  left++;
              }else{
                  res+=r_max-height[right];
                  right--;
              }
          }
          return res;
      }
  }
  边计算边取值，很强。
  时间复杂度：O(n)
  空间复杂度：O(1)
  

  0 赞同 0 条回复

  登录以回复
• 白雪公主倒拔垂杨柳 永久会员 2024年4月6日 下午3:19

  • 备忘录优化，Java版本

  class Solution {
      public int trap(int[] height) {
          if(height==null || height.length<=1) return 0;
          int n=height.length;
  
          int ans=0;//储水面积
          int[] l_max = new int[n];
          int[] r_max = new int[n]; 
  
          //l_max[i]表示位置 i 左边最高的柱子高度
          //r_max[i]表示位置 i 右边最高的柱子高度
          l_max[0]=height[0]; //坐标范围都是0到n-1
          r_max[n-1]=height[n-1];
  
          // 能蓄水的位置的下标：1到n-1
          for(int i=1;i<n;i++){
              l_max[i]=Math.max(height[i],l_max[i-1]);
          }
          for(int j=n-2;j>=0;j--){
              r_max[j]=Math.max(height[j],r_max[j+1]);
          }
          for(int i=1;i<=n-1;i++){
              ans+=Math.min(l_max[i],r_max[i])-height[i];
          }
  
          return ans;
      }
  }
  

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

  在备忘录解法中，l_max[i]和r_max[i]代表的是height[0..i]和height[i..end]的最高柱子高度。
  在双指针解法中，l_max和r_max代表的是height[0..left]和height[right..end]的最高柱子高度。

  • 双指针版本

  class Solution {
      public int trap(int[] height) {
          if(height==null || height.length<=1) return 0;
          int n=height.length;
  
          int ans=0;//储水面积
          int l_max=0;
          int r_max=0;
  
          int left=0;
          int right=n-1;
  
          while(left<=right){
              l_max=Math.max(l_max,height[left]);
              r_max=Math.max(r_max,height[right]);
  
              if(l_max<r_max){
                  ans+=l_max-height[left];
                  left++;
              }else{
                  ans+=r_max-height[right];
                  right--;
              }
          }
  
          return ans;
      }
  }
  

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

  0 赞同 0 条回复

  登录以回复
• Raphtalia. 普通 2024年4月4日 下午8:00

  class Solution {
  public:
  int trap(vector& height) {
  int n = height.size();
  if(n 0) return 0;
  vector l(n), r(n);
  int res = 0;
  l[0] = height[0], r[n – 1] = height[n – 1];
  // res += min(l[i], r[i]) – height[i]
  for(int i = 1; i < n; i ++) {
  l[i] = max(l[i – 1], height[i]);
  }
  for(int i = n – 2; i >= 0; i –) {
  r[i] = max(r[i + 1], height[i]);
  }
  for(int i = 0; i < n; i ++) {
  res += min(l[i], r[i]) – height[i];
  }
  return res;
  }
  };
  时空复杂度
  O(N)

  0 赞同 0 条回复

  登录以回复
• heathhou 普通 2024年4月2日 下午11:40

  class Solution {
  public:
      int trap(vector<int>& height) {
          if(height.empty())
              return 0;
  
          int n = height.size();
          int ans = 0;
  
  
          int left = 0;
          int right = n - 1;
  
          int l_max = height[0];
          int r_max = height[n - 1];
  
          while(left <= right){
              l_max = max(l_max, height[left]);
              r_max = max(r_max, height[right]);
  
              // 只要min(l_max, r_max) - height[] 就可以了，另一个大的是不是左边/右边最高的不重要
              if(l_max < r_max){
                  ans += l_max - height[left];
                  left++;
              }else{
                  ans += r_max - height[right];
                  right--;
              }
          }
  
          return ans;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 紫芝 普通 2024年4月2日 下午10:33

  思路：两次遍历，第一次正序遍历，记录每个位置的左边最大值；第二次逆序遍历，记录每个位置的右边最大值。

  “`c++
  class Solution {
  public:
  int trap(vector& height) {
  int n = height.size();
  vector leftHeight(n, 0);
  int maxiL = height[0];
  for (int i=1; i=1; i–) {
  if (height[i] > maxiR) {
  maxiR = height[i];
  } else if (height[i] <= leftHeight[i]) { res += min(maxiR, leftHeight[i]) - height[i]; }

      }
      return res;
  }
  

  };

  “`

  0 赞同 0 条回复

  登录以回复