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

共以下 5 个回答

• 陆狗陆狗 普通 2024年12月31日 下午10:00

  解题思路
  – 定义2个dp： int[] leftdp 在i时左边的最大值； int[] rightdp 在i时右边的最大值
  – 在i点，取 leftdp[i]、rightdp[i]的最小值最为容器的高
  – 容量=宽（1）*高，其中高=容器的高-height[i]
  【题解1】

  class Solution {
      public int trap(int[] height) {
          // 定义2个dp： int[] leftdp 在i时左边的最大值； int[] rightdp 在i时右边的最大值
          // 在i点，取 leftdp[i]、rightdp[i]的最小值最为容器的高
          // 容量=宽1*高，其中高=容器的高-height[i]
  
          int[] leftdp = new int[height.length];
          leftdp[0] = height[0];
          for (int i = 1; i < height.length; i++) {
              leftdp[i] = Math.max(leftdp[i - 1], height[i]);
          }
  
          int[] rightdp = new int[height.length];
          rightdp[height.length - 1] = height[height.length - 1];
          // 【错误点】rightdp初始化写成了leftdp
          for (int i = height.length - 2; i >= 0; i--) {
              rightdp[i] = Math.max(rightdp[i + 1], height[i]);
          }
  
          // 遍历(开头和结尾都没办法接水)
          int result = 0;
          for (int i = 1; i < height.length - 1; i++) {
              // 容器的高
              int boxHeight = Math.min(leftdp[i], rightdp[i]);
              // 能用到的高
              result = result + (boxHeight - height[i]);
  
          }
  
          return result;
  
      }
  }
  

  • 错误点1：rightdp初始化写成了leftdp

  0 赞同 0 条回复

  登录以回复
• Pendulumpal 普通 2024年12月25日 下午9:29

  单调栈解法O(n)

  class Solution {
     public int trap(int[] height) {
          if (height == null || height.length == 0) {
              return 0;
          }
          int n = height.length;
          int totalWater = 0;
          java.util.Stack<Integer> stack = new java.util.Stack<>();
          for (int i = 0; i < n; i++) {
              while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                  int top = stack.pop(); // 当前柱子的索引
                  if (stack.isEmpty()) {
                      break; // 栈为空时无法形成凹槽
                  }
                  int left = stack.peek(); // 左边界的索引
                  int width = i - left - 1; // 两柱子之间的宽度
                  int boundedHeight = Math.min(height[i], height[left]) - height[top]; // 有效的高度
                  totalWater += width * boundedHeight; // 计算当前凹槽可以存的水量
              }
  
              stack.push(i); // 将当前柱子的索引入栈
          }
  
          return totalWater;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月24日 下午3:41

  class Solution {
  public:
      int trap(vector<int>& height) {
          int n = height.size();
          int res = 0;
          vector<int> left(n, 0);
          vector<int> right(n, 0);
          left[0] = height[0];
          right[n - 1] = height[n - 1];
          for(int i = 1; i < n; i++) {
              left[i] = max(left[i - 1], height[i]);
          }
          for(int i = n - 2; i >= 0; i--) {
              right[i] = max(right[i + 1], height[i]);
          }
          for(int i = 0; i < n; i++) {
              res += min(left[i], right[i]) - height[i];
          }
          return res;
      }
  };
  

  使用两个数组分别记录左边最高的柱子与右边最高的柱子，雨水量为柱子高度的最小值减去高度。
  时间复杂度O(N)，空间复杂度O(N)。

  0 赞同 0 条回复

  登录以回复
• 月下足迹 普通 2024年12月24日 上午10:10

  //双指针解法
  class Solution {
  public int trap(int[] height) {
  if (height null || height.length 0) {
  return 0;
  }

      int left = 0, right = height.length - 1; // 双指针
      int leftMax = 0, rightMax = 0; // 左右两边最大高度
      int water = 0; // 存储雨水总量
  
      while (left < right) {
          if (height[left] < height[right]) {
              // 如果左边较低，更新左边最大值或计算雨水
              if (height[left] >= leftMax) {
                  leftMax = height[left];
              } else {
                  water += leftMax - height[left];
              }
              left++;
          } else {
              // 如果右边较低，更新右边最大值或计算雨水
              if (height[right] >= rightMax) {
                  rightMax = height[right];
              } else {
                  water += rightMax - height[right];
              }
              right--;
          }
      }
  
      return water;
  }
  

  }

  0 赞同 0 条回复

  登录以回复
• 秋山丽奈 普通 2024年12月23日 下午8:25

  思路： 使用单调栈处理

  class Solution {
      public int trap(int[] height) {
          Stack<Integer> stack = new Stack<Integer>();
          stack.push(0);
  
          int sum = 0;
  
          for(int i = 1; i < height.length; i ++){
              int current = height[i];
              int popNum = stack.peek();
  
              if(current <= height[popNum]){
                  stack.push(i);
              }else if(current > height[popNum]){
                  // 当前遇到 一个更高的 计算 体积  
                  while(!stack.isEmpty() && current > height[popNum]){
  
                      popNum = stack.pop();
                      if(stack.isEmpty()){
                          break;
                      }
                      int left = stack.peek();
  
                      int waterWidth = i - left - 1;
                      int waterHeight = Math.min(height[left], current) - height[popNum];
                      sum += (waterHeight * waterWidth);
                      popNum = stack.peek();
  
  
                  }
                  stack.push(i);
  
              }
  
  
          }
  
          return sum;
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复