3479. 将水果装入篮子 III(中等)

Posted on In Views:

1，问题描述

力扣第440周赛-第三题

3479. 将水果装入篮子 III

难度：中等

给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。

你需要对 fruits 数组从左到右按照以下规则放置水果：

  • 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
  • 每个篮子只能装 一种 水果。
  • 如果一种水果 无法放入 任何篮子，它将保持 未放置。

返回所有可能分配完成后，剩余未放置的水果种类的数量。

示例 1

输入： fruits = [4,2,5], baskets = [3,5,4]

输出： 1

解释：

  • fruits[0] = 4 放入 baskets[1] = 5。
  • fruits[1] = 2 放入 baskets[0] = 3。
  • fruits[2] = 5 无法放入 baskets[2] = 4。

由于有一种水果未放置，我们返回 1。

示例 2

输入： fruits = [3,6,1], baskets = [6,4,7]

输出： 0

解释：

  • fruits[0] = 3 放入 baskets[0] = 6。
  • fruits[1] = 6 无法放入 baskets[1] = 4（容量不足），但可以放入下一个可用的篮子 baskets[2] = 7。
  • fruits[2] = 1 放入 baskets[1] = 4。

由于所有水果都已成功放置，我们返回 0。

提示：

  • n == fruits.length == baskets.length
  • 1 <= n <= 10^5
  • 1 <= fruits[i], baskets[i] <= 10^9

2，初步思考

​ 与前3477. 将水果放入篮子 II这一题逻辑是一致的，只是数据量变得很大

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import support.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class _3479将水果装入篮子III {

    // 解法1：区间树
    // 本题与第一题本质是一道题，只是要求了时间复杂度较低
    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {

        // 1，生成区间树
        List<TreeNode> tempBefore = new ArrayList<>();
        List<TreeNode> tempCur = new ArrayList<>();
        for (int i = 0; i < baskets.length; i++) {
            tempBefore.add(new TreeNode(baskets[i]));
        }
        TreeNode root = null;
        while (!tempBefore.isEmpty()) {
            int size = tempBefore.size();
            boolean flag = size % 2 == 1;
            for (int i = 0; i < size / 2; i++) {
                int index = i * 2;
                TreeNode left = tempBefore.get(index);
                TreeNode right = tempBefore.get(index + 1);
                root = new TreeNode(Math.max(left.val, right.val), left, right);
                if (size != 2) tempCur.add(root);
            }
            if (flag) {
                TreeNode left = tempBefore.get(size - 1);
                root = new TreeNode(left.val, left, null);
                if (size != 1)tempCur.add(root);
            }
            tempBefore = tempCur;
            tempCur = new ArrayList<>();
        }

        // 搜索区间树
        int counter = fruits.length;
        for (int i = 0; i < fruits.length; i++) {
            if (root.val >= fruits[i]) {
                update(root, fruits[i]);
                counter--;
            }
        }

        return counter;
    }

    // 搜索and更新区间树
    private int update(TreeNode root, int val) {
        // 没有找到合适的数值，直接返回
        if (root == null) {
            return -1;
        } else if (root.val < val) {
            return root.val;
        }

        int temp = root.val;
        // 有合适的数据（root.val>=val）,需要删除这个数据
        if (root.left != null && root.left.val >= val) {
            // 左边大
            root.val = Math.max(update(root.left, val), root.right != null ? root.right.val : -1);
            return root.val;
        } else if (root.right != null && root.right.val >= val) {
            // 右边大
            root.val = Math.max(update(root.right, val), root.left != null ? root.left.val : -1);
            return root.val;
        } else {
            // 没有子节点
            root.val = -1;
            return -1;
        }
    }

    public static void main(String[] args) {
        _3479将水果装入篮子III test = new _3479将水果装入篮子III();
//        System.out.println(test.numOfUnplacedFruits(new int[]{1,2,3,2,2}, new int[]{3,1}));
//        System.out.println(test.numOfUnplacedFruits(new int[]{4, 2, 5}, new int[]{3, 5, 4}));
//        System.out.println(test.numOfUnplacedFruits(new int[]{31}, new int[]{6}));
        System.out.println(test.numOfUnplacedFruits(new int[]{39,10,21,40}, new int[]{39,57,37,63}));
//        System.out.println(test.numOfUnplacedFruits(new int[]{3, 6, 1}, new int[]{6, 4, 7}));
    }
}

参考链接：

https://www.bilibili.com/video/BV15gRaYZE5o/?t=44m20s&vd_source=071ecfeeef39b447b8df51119337453a