Zolostays

01Range Sum

Return the number of range sums that lie in [lower, upper] inclusive.

Example 1

Input:

arr = [-2, 5, -1]
lower = -2
upper = 2

Output:

Explanation: There are three ranges with sums that fall within the range [-2, 2]:

[-2] with sum -2
[-2, 5, -1] with sum 2
[-1] with sum -1

Example 2

Input:

arr = [1, -3, 5, 2, 5, 2, -5]
lower = -2
upper = 6

Output:

Explanation: There are eight ranges with sums that fall within the range [-2, 6].

Example 3

Input:

arr = [1, -3, 5, -2, 2, 5, -1, 10]
lower = 5
upper = 9

Output:

Explanation: There are twelve ranges with sums that fall within the range [5, 9].

LC 327 模板：归并排序前缀和。设 S[i] 为前缀和，区间 (i, j] 的和落在 [lower, upper] 等价于 S[j] - S[i] ∈ [lower, upper]，即 S[j] ∈ [S[i]+lower, S[i]+upper]。在归并左右两半时，左半固定 i，对右半已排序的 S[j] 用 bisect 计数。时间复杂度 O(n log n)，空间复杂度 O(n)。

from typing import List
from bisect import bisect_left, bisect_right

def countRangeSum(arr: List[int], lower: int, upper: int) -> int:
    n = len(arr)
    pref = [0] * (n + 1)
    for i, v in enumerate(arr):
        pref[i + 1] = pref[i] + v

    def merge_sort(lo: int, hi: int) -> int:
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        cnt = merge_sort(lo, mid) + merge_sort(mid, hi)
        right = pref[mid:hi]
        for x in pref[lo:mid]:
            cnt += bisect_right(right, x + upper) - bisect_left(right, x + lower)
        pref[lo:hi] = sorted(pref[lo:hi])
        return cnt

    return merge_sort(0, n + 1)

class Solution {
    int countRangeSum(int[] arr, int lower, int upper) {
        int n = arr.length;
        long[] pref = new long[n + 1];
        for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
        return (int) mergeSort(pref, 0, n + 1, lower, upper);
    }

    private long mergeSort(long[] pref, int lo, int hi, int lower, int upper) {
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) / 2;
        long cnt = mergeSort(pref, lo, mid, lower, upper) + mergeSort(pref, mid, hi, lower, upper);
        long[] right = Arrays.copyOfRange(pref, mid, hi);
        for (int i = lo; i < mid; i++) {
            long target1 = pref[i] + lower, target2 = pref[i] + upper;
            int l = lower_bound(right, target1), r = upper_bound(right, target2);
            cnt += r - l;
        }
        long[] merged = new long[hi - lo];
        int p = lo, q = mid, k = 0;
        while (p < mid && q < hi) merged[k++] = pref[p] <= pref[q] ? pref[p++] : pref[q++];
        while (p < mid) merged[k++] = pref[p++];
        while (q < hi) merged[k++] = pref[q++];
        System.arraycopy(merged, 0, pref, lo, merged.length);
        return cnt;
    }

    private int lower_bound(long[] a, long v) {
        int lo = 0, hi = a.length;
        while (lo < hi) { int m = (lo + hi) >>> 1; if (a[m] < v) lo = m + 1; else hi = m; }
        return lo;
    }

    private int upper_bound(long[] a, long v) {
        int lo = 0, hi = a.length;
        while (lo < hi) { int m = (lo + hi) >>> 1; if (a[m] <= v) lo = m + 1; else hi = m; }
        return lo;
    }
}

class Solution {
public:
    int countRangeSum(vector<int>& arr, int lower, int upper) {
        int n = arr.size();
        vector<long long> pref(n + 1, 0);
        for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
        return mergeSort(pref, 0, n + 1, lower, upper);
    }

private:
    long long mergeSort(vector<long long>& pref, int lo, int hi, int lower, int upper) {
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) / 2;
        long long cnt = mergeSort(pref, lo, mid, lower, upper) + mergeSort(pref, mid, hi, lower, upper);
        vector<long long> right(pref.begin() + mid, pref.begin() + hi);
        for (int i = lo; i < mid; i++) {
            auto l = lower_bound(right.begin(), right.end(), pref[i] + lower);
            auto r = upper_bound(right.begin(), right.end(), pref[i] + upper);
            cnt += r - l;
        }
        inplace_merge(pref.begin() + lo, pref.begin() + mid, pref.begin() + hi);
        return cnt;
    }
};

02Trapping Rain Water

Given n non-negative integers repres

Constraints

n == height.length
`1

Example 1

Input:

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2

Input:

height = [4,2,0,3,2,5]

Output:

Explanation: No explanation provided.

解法

LC 42 标准双指针。l, r 从两端往中间走，维护 lmax, rmax。若 height[l] < height[r]，那么 l 处能积水量 = lmax - height[l]，更新 lmax 并 l++；反之同理处理 r。时间复杂度 O(n)，空间复杂度 O(1)。

from typing import List

def trap(height: List[int]) -> int:
    l, r = 0, len(height) - 1
    lmax = rmax = 0
    ans = 0
    while l < r:
        if height[l] < height[r]:
            if height[l] >= lmax:
                lmax = height[l]
            else:
                ans += lmax - height[l]
            l += 1
        else:
            if height[r] >= rmax:
                rmax = height[r]
            else:
                ans += rmax - height[r]
            r -= 1
    return ans

class Solution {
    int trap(int[] height) {
        int l = 0, r = height.length - 1, lmax = 0, rmax = 0, ans = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (height[l] >= lmax) lmax = height[l]; else ans += lmax - height[l];
                l++;
            } else {
                if (height[r] >= rmax) rmax = height[r]; else ans += rmax - height[r];
                r--;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = (int)height.size() - 1, lmax = 0, rmax = 0, ans = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (height[l] >= lmax) lmax = height[l]; else ans += lmax - height[l];
                l++;
            } else {
                if (height[r] >= rmax) rmax = height[r]; else ans += rmax - height[r];
                r--;
            }
        }
        return ans;
    }
};