LeetCode每日一题，8-6

水果成篮3️⃣
本题给你两个数组fruits和baskets，对于fruits种的每个数，找到baskets中第一个大于等于fruits的值，然后baskets的该下标作废，最后返回有多少个fruit找不到对应的baskets。
用线段树维护区间最大值，然后对于每个fruits进行查询，重点是查询最左边的值。

class Solution {int N = (int) (1e5 + 10);Node[] tr = new Node[4 * N];class Node {int l, r;int val;}void build(int u, int l, int r,  int[] baskets) {tr[u] = new Node();tr[u].l = l;tr[u].r = r;tr[u].val = 0;if (l == r) {tr[u].val = baskets[l - 1];return;}int mid = l + r >> 1;build(u << 1, l, mid, baskets);build(u << 1 | 1, mid + 1, r, baskets);tr[u].val = Math.max(tr[u << 1].val, tr[u << 1 | 1].val);}int query(int u, int l, int r, int val) {// 如果当前节点的值小于要查询的值，直接返回0if (tr[u].val < val) {return 0;}// 如果当前节点区间完全在查询区间外，返回0if (tr[u].r < l || tr[u].l > r) {return 0;}// 如果是叶子节点且值满足条件if (tr[u].l == tr[u].r) {int pos = tr[u].l;tr[u].val = -1;  // 标记为已使用return pos;}int res = 0;int mid = (tr[u].l + tr[u].r) >> 1;// 先尝试左子树if (tr[u << 1].val >= val && l <= mid) {res = query(u << 1, l, Math.min(r, mid), val);}// 如果左子树没找到结果且右子树可能有解，尝试右子树if (res == 0 && tr[u << 1 | 1].val >= val && r > mid) {res = query(u << 1 | 1, Math.max(l, mid + 1), r, val);}// 更新当前节点的值tr[u].val = Math.max(tr[u << 1].val, tr[u << 1 | 1].val);return res;}public int numOfUnplacedFruits(int[] fruits, int[] baskets) {int n = fruits.length;int m = baskets.length;int res = n;build(1, 1, m, baskets);for (int i = 0; i < n; i++) {int val = fruits[i];
//            找到第一个大于等于val的位置int pos = query(1, 1, m, val);if(pos != 0)res --;}return res;}
}