题解 | #接雨水问题#
接雨水问题
https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
#include <algorithm> class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 */ long long maxWater(vector<int>& arr) { // write code here // step 1:检查数组是否为空的特殊情况 // step 2:准备双指针,分别指向数组首尾元素,代表最初的两个边界 // step 3:指针往中间遍历,遇到更低柱子就是底,用较短的边界减去底就是这一列的接水量,遇到更高的柱子就是新的边界,更新边界大小。 if (arr.size()==0) { return 0; } int left=0,right=arr.size()-1,maxL=0,maxR=0; long long res=0; while (left<right) { maxL=max(maxL, arr[left]); maxR=max(maxR,arr[right]); if (maxL<maxR) { res+=maxL-arr[left++]; }else { res+=maxR-arr[right--]; } } return res; } };