共以下 10 个回答

• yxy 普通 2023年7月25日 下午4:16

  好难

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

  0 赞同 0 条回复

  登录以回复
• 张开怀 普通 2023年7月24日 下午7:31

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

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

  0 赞同 0 条回复

  登录以回复
• mpweixin用户 永久会员 2023年7月23日 下午7:52

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

  0 赞同 0 条回复

  登录以回复
• Dsjh 普通 2023年7月23日 下午5:21

  MY

  class Solution {
  public:
      int trap(vector<int>& height) {
          if(height.size()==1){
              return 0;
          }
          int l_maxht=0,r_maxht=0;
          int l=0,r=height.size()-1;
          int ans=0;
          // 寻找每根柱子左右两侧最大值较小的那个
          while(l<r){
              l_maxht = max(l_maxht,height[l]);
              r_maxht = max(r_maxht,height[r]);
              if(l_maxht<r_maxht){
                  ans+=l_maxht-height[l];
                  l++;
              }
              else{
                  ans+=r_maxht-height[r];
                  r--;
              }
          }
          return ans;
  
  
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 哈哈哈哈开开心心 普通 2023年7月23日 上午4:58

  class Solution:
      def trap(self, height: List[int]) -> int:
          l, r = 0, len(height) - 1
          l_max, r_max = height[l], height[r]
          res = 0
  
          while l <= r:
              l_max = max(l_max, height[l])
              r_max = max(r_max, height[r])
  
              if (l_max < r_max):
                  res += l_max - height[l]
                  l += 1
              else:
                  res += r_max - height[r]
                  r -= 1
  
          return res
  

  双指针

  0 赞同 0 条回复

  登录以回复
• BOZ 普通 2023年7月22日 下午3:45

  【思路】双指针法
  【复杂度】时间O(n)，空间O(1)

  class Solution {
  public:
      int trap(vector& height) {
          int result = 0;
          int l = 0, r = height.size() - 1;
          int l_max = 0, r_max = 0;
  
          while(l <= r) {
              l_max = max(l_max, height[l]);
              r_max = max(r_max, height[r]);
  
              if (l_max < r_max) result += l_max - height[l++];
              else result += r_max - height[r--];
          }
  
          return result;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• Vow the vow。 普通 2023年7月22日 上午11:50

  用两次dp

  public int trap(int[] height) {
          int n = height.length;
          int[] left = new int[n];
          int[] right = new int[n];
          for(int i = 1; i < n; i++){
              left[i] = Math.max(left[i-1],height[i-1]);
          }
          for(int i = n-2; i > 0; i--){
              right[i] = Math.max(right[i+1],height[i+1]);
          }
          int res = 0;
          for(int i = 1; i < n-1; i++){
              System.out.println(left[i] +"  " + right[i]);
              int temp = Math.min(left[i],right[i]);
              if(temp > height[i]){
                  res +=  temp - height[i];
              }
  
          }
          return res;
      }
  

  0 赞同 0 条回复

  登录以回复
• 花老爷 普通 2023年7月21日 下午5:32

  动态规划
  时间：O(n)
  空间：O(n)

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

  0 赞同 0 条回复

  登录以回复
• 怀瑾 永久会员 2023年7月21日 下午3:34

  “`C++
  int trap(vector& height) {
  int n = height.size();
  if (n < 3) { return 0; // 如果柱子数量小于3，则无法容纳雨水 }

  int left = 0, right = n - 1; // 左右指针
  int leftMax = 0, rightMax = 0; // 记录左右两侧的最大高度
  int result = 0; // 最大雨水容量
  
  while (left < right) {
      if (height[left] < height[right]) {
          if (height[left] > leftMax) {
              leftMax = height[left]; // 更新左侧最大高度
          } else {
              result += leftMax - height[left]; // 计算当前位置可以容纳的雨水量
          }
          left++;
      } else {
          if (height[right] > rightMax) {
              rightMax = height[right]; // 更新右侧最大高度
          } else {
              result += rightMax - height[right]; // 计算当前位置可以容纳的雨水量
          }
          right--;
      }
  }
  
  return result;
  

  }

  “`

  0 赞同 0 条回复

  登录以回复
• Yodl. 普通 2023年7月21日 下午3:30

  class Solution 
  {
  public:
      int trap(vector<int>& height) 
      {
          int n = height.size();
          // 定义两个 dp 数组，一个表示从左边开始的最大值，一个表示从右边开始的最大值
          vector<int> leftdp(n), rightdp(n); 
  
          // 先填左侧的
          leftdp[0] = height[0]; // 初始化
          for(int i = 1; i < n; i++)
              leftdp[i] = max(leftdp[i - 1], height[i]); 
  
          // 再填右侧的
          rightdp[n - 1] = height[n - 1]; // 初始化
          for(int i = n - 2; i >= 0; i--)
              rightdp[i] = max(rightdp[i + 1], height[i]);
  
          // 累加每一个柱子上方的雨水量
          int ret = 0;
          for(int i = 1; i < n - 1; i++) // 最左侧和最右侧不用求
              ret += min(leftdp[i], rightdp[i]) - height[i];
  
          return ret;
      }
  };
  

  0 赞同 0 条回复

  登录以回复