leetcode

42.接雨水

力扣链接

超时

class Solution{
public:
  int trap(std::vector<int>& height){
    int left = 0, right = height.size() - 1, leftmax = 0, rightmax = 0, res = 0;
    while (left < right){
        if (height[left] < height[right]){
            if (height[left] >= leftmax) leftmax = height[left];
            else {
                res += leftmax - height[left];
                left++;
            }
        } else {
            if (height[right] >= rightmax) rightmax = height[right];
            else {
               res += rightmax - height[right];
               right--;
           }
        }
    }
    return res;
  }
}; 

优化

class Solution{
public:
  int trap(std::vector<int>& height){
    int left = 0, right = height.size() - 1, leftmax = 0, rightmax = 0, res = 0;
    while (left < right){
        leftmax = std::max(leftmax, height[left]);
        rightmax = std::max(rightmax, height[right]);
        if (height[left] < height[right]){
            res += leftmax - height[left];
            left++;
        } else {
            res += rightmax - height[right];
            right--;
        }
    }
    return res;
  }
}; 

This site is open source. Improve this page.