灵茶山算法基础笔记

class SegmentTree {
    private final int[] max;

    public SegmentTree(int[] a) {
        int n = a.length;
        //max是​​大于或等于 n的最小的 2 的幂次方​​
        max = new int[2 << (32 - Integer.numberOfLeadingZeros(n - 1))];
        //建立线段树
        build(a, 1, 0, n - 1);
    }

    // 找区间内的第一个 >= x 的数，并更新为 -1，返回这个数的下标（没有则返回 -1）
    //o为第几个位置 l为左下标 r为右下标 x为目标数
    public int findFirstAndUpdate(int o, int l, int r, int x) {
        if (max[o] < x) { // 区间没有 >= x 的数
            return -1;
        }
        if (l == r) {
            max[o] = -1; // 更新为 -1，表示不能放水果
            return l;
        }
        int m = (l + r) / 2;
        int i = findFirstAndUpdate(o * 2, l, m, x); // 先递归左子树
        if (i < 0) { // 左子树没找到
            i = findFirstAndUpdate(o * 2 + 1, m + 1, r, x); // 再递归右子树
        }
        maintain(o);
        return i;
    }
    //在回溯过程更新节点
    private void maintain(int o) {
        max[o] = Math.max(max[o * 2], max[o * 2 + 1]);
    }

    // 初始化线段树
    private void build(int[] a, int o, int l, int r) {
        if (l ==  r) {
            max[o] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, o * 2, l, m);
        build(a, o * 2 + 1, m + 1, r);
        maintain(o);
    }
}

class Solution {
    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        SegmentTree t = new SegmentTree(baskets);
        int n = baskets.length;
        int ans = 0;
        for (int x : fruits) {
            if (t.findFirstAndUpdate(1, 0, n - 1, x) < 0) {
                ans++;
            }
        }
        return ans;
    }
}