题解 | #接雨水问题#

接雨水问题

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

class Solution {
  public:
    long long sumPlus(long long i, long long j, vector<int>& arr,
                      long long maxIndex = -1) {
        if ((maxIndex - i) <= 1)
            return 0;
        long long minV = min(arr[i], arr[j]);
        long long sum = 0;
        long long sumlow = 0;
        if (maxIndex > 0) {
            while (j <= maxIndex) {
                long long minV = min(arr[i], arr[j]);
                if (arr[i] > arr[j]) {
                    sumlow += minV;
                    j++;
                } else {
                    sum += ((j - i + 1) * minV - (2 * minV + sumlow));
                    i = j;
                    j++;
                    sumlow = 0;
                }
            }
        }
        return sum >= 0 ? sum : 0;
    }

    long long maxWater(vector<int>& arr) {
        int len = arr.size();
        if (len < 2)
            return 0;
        long long sum = 0;
        auto iteratorMaxN = max_element(arr.begin(), arr.end());
        long long maxN = *iteratorMaxN;
        long long maxNIndex = distance(arr.begin(), iteratorMaxN);
        sum += sumPlus(0, 1, arr, maxNIndex);
        if (len - maxNIndex >= 2) {
            reverse(arr.begin() + maxNIndex, arr.end());
            sum += sumPlus(maxNIndex, maxNIndex + 1, arr, len - 1);
        }
        return sum;
    }
};

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务