题解 | #接雨水问题#

接雨水问题

https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // 双指针
        int left=0;
        int right=arr.size()-1;
        int sum=0;
        int leftval=arr[0];
        int rightval=arr[right];
        left++;
        right--;
        while(left<=right)
        {
            if(leftval<rightval)
            {
                sum+=leftval-arr[left]>0?leftval-arr[left]:0;
                if(arr[left]>leftval)
                leftval=arr[left];
                left++;
            }else
            {
               
                sum+=rightval-arr[right]>0?rightval-arr[right]:0;
                if(arr[right]>rightval)
                  rightval=arr[right];
                right--; 
            }
        }
        return sum;

    }
};

维护左右俩边的最大值,有一点点贪心的思想,就是左右俩边的值谁大那么谁就可以兜底,我们就用小的那一边去计算水的存储容量。

全部评论

相关推荐

10-30 22:18
已编辑
毛坦厂中学 C++
点赞 评论 收藏
分享
11-03 14:38
重庆大学 Java
AAA求offer教程:我手都抬起来了又揣裤兜了
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务