LC 2736. 最大和查询

题目描述

这是 LeetCode 上的 2736. 最大和查询 ，难度为 困难。

给你两个长度为 n、下标从 0 开始的整数数组 nums1 和 nums2，另给你一个下标从 1 开始的二维数组 queries，其中 $queries[i] = [x{i}, y{i}]$ 。

对于第 i 个查询，在所有满足 $nums1[j] >= x{i}$ 且 $nums2[j] >= y{i}$ 的下标 j ($0 <= j < n$) 中，找出 $nums1[j] + nums2[j]$ 的 最大值 ，如果不存在满足条件的 j 则返回 $-1$。

返回数组 answer，其中 answer[i] 是第 i 个查询的答案。

示例 1：

1
2
3
4
5
6
7
8
9
输入：nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]

输出：[6,10,7]

解释：
对于第 1 个查询：xi = 4 且 yi = 1 ，可以选择下标 j = 0 ，此时 nums1[j] >= 4 且 nums2[j] >= 1 。nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。
对于第 2 个查询：xi = 1 且 yi = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。
对于第 3 个查询：xi = 2 且 yi = 5 ，可以选择下标 j = 3 ，此时 nums1[j] >= 2 且 nums2[j] >= 5 。nums1[j] + nums2[j] 等于 7 ，可以证明 7 是可以获得的最大值。
因此，我们返回 [6,10,7] 。

示例 2：
1
2
3
4
5
输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]

输出：[9,9,9]

解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。

示例 3：
1
2
3
4
5
输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]

输出：[-1]

解释：示例中的查询 xi = 3 且 yi = 3 。对于每个下标 j ，都只满足 nums1[j] < xi 或者 nums2[j] < yi 。因此，不存在答案。

提示：

  • $nums1.length = nums2.length$
  • $n = nums1.length$
  • $1 <= n <= 10^5$
  • $1 <= nums1[i], nums2[i] <= 10^9$
  • $1 <= queries.length <= 10^5$
  • $queries[i].length = 2$
  • $x_{i} = queries[i][1]$
  • $y_{i} = queries[i][2]$
  • $1 <= x{i}, y{i} <= 10^9$

离散化 + 排序 + 树状数组

根据题意，两个等长数组 num1 和 nums2，只能是相同下标的元素凑成一对。

不妨用两个一维数组 nums1 和 nums2 构建出一个二维数组 nums，方便后续处理，其中 $nums[i] = [nums1[i], nums2[i]]$。

同时对 queries 进行简单拓展，构建新的二维数组 nq，目的是对原有下标信息进行记录，其中 $nq[i] = [queries[i][0], queries[i][1], i]$（此处构建新 nq 的作用，下文会说）。

好了，现在我们有两个新的数组 nums 和 nq，接下来所有讨论都会针对新数组进行。

希望你牢牢记住：$nums[i] = [nums1[i], nums2[i]]$ 是对 nums1 和 nums2 的简单合并；而 $nq[i] = [queries[i][0], queries[i][1], i]$ 是对 queries 原有下标的拓展记录。

做完简单的预处理工作后，来思考一个前置问题：

假设其他内容不变，要求从满足「$nums[j][0] \geq nq[i][0]$ 且 $nums[j][1] \geq nq[i][1]$」调整为仅需满足「$nums[j][0] \geq nq[i][0]$」，如何求解？

一个简单的做法：

  1. 对 nums 中的第一维（即 $nums[i][0] = nums1[i]$）和 nq 中第一维（即 $nq[i][0] = queries[i][0] = x_{i}$）排倒序；

  2. 从前往后处理每个询问 $nq[i]$，同时使用变量 idx 对 nums 进行扫描，若满足 $nums[idx][0] \geq nq[i][0]$ 时，将 idx 右移，同时记录已被扫描的数对和 $nums[idx’][0] + nums[idx’][1]$ 。

    当 idx 不能再后移时，说明当前所有满足 $nums[idx][0] \geq nq[i][0]$ 要求的数对已被扫描完，在记录的数对和中取最大值，即是当前询问 $nq[i]$ 的答案 $ans[nq[i][2]]$（此处解释了为什么需要构造新数组 nq，因为询问处理是按照排序后进行，但在 ans 中需要映射回原有顺序）。

  3. 重复步骤 $2$，直到处理完所有询问。

搞懂前置问题后，回到原问题，需要满足「$nums[j][0] \geq nq[i][0]$ 且 $nums[j][1] \geq nq[i][1]$」要求。

进一步思考，排序 + 调整询问顺序，只能解决其中一维限制要求，另一维该如何处理？

或更直接的问题：如何在被记录的所有数对和 $nums[idx’][0] + nums[idx’][1]$ 中找出那些满足 $nums[j][1] \geq nq[i][1]$ 的最大数对和。

不失一般性，假设当前处理到的是 $nums[idx]$，其中 $nums[idx][0]$ 的限制要求，通过前置问题的排序方式解决了。另外的 $nums[idx][1]$ 我们希望作为“位置信息”，数对和 $sum = nums[idx][0] + nums[idx][1]$ 作为“值信息”进行记录。

由于条件 $1 \leq x{i}, y{i} \leq 1e9$，我们需要对将要作为“位置信息”添加到树状数组的 $nums[idx][1]$ 和 $nq[i][1]$ 进行离散化，将其映射到 $[0, m - 1]$ 范围内。

对于每个询问，都需要找到已遍历过的大于 $nq[i][1]$ 的位置上的最大值，把离散化后的值域换成数组坐标，相当于求后缀最大值，后缀最大值可通过相反数，变成求前缀最大值。

能够实现类似的前缀操作，支持“单点修改”和“区间查询”的数据结构是「树状数组」。

Java 代码：

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
class Solution {
    int sz;
    int[] tr;
    int lowbit(int x) {
        return x & -x;
    }
    void add(int a, int b) {
        for (int i = a; i <= sz; i += lowbit(i)) tr[i] = Math.max(tr[i], b);
    }
    int query(int x) {
        int ans = -1;
        for (int i = x; i > 0; i -= lowbit(i)) ans = Math.max(ans, tr[i]);
        return ans;
    }
    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length, m = queries.length;
        // 构建新的 nums 和 nq
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; i++) nums[i] = new int[]{nums1[i], nums2[i]};
        int[][] nq = new int[m][3];
        for (int i = 0; i < m; i++) nq[i] = new int[]{queries[i][0], queries[i][1], i};

        // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
        Set<Integer> set = new HashSet<>();
        for (int[] x : nums) set.add(x[1]);
        for (int[] q : nq) set.add(q[1]);
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        sz = list.size();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sz; i++) map.put(list.get(i), i);

        // 调整询问顺序, 解决其中一维限制
        Arrays.sort(nums, (a,b)->b[0]-a[0]);
        Arrays.sort(nq, (a,b)->b[0]-a[0]);

        tr = new int[sz + 10];
        Arrays.fill(tr, -1);

        int[] ans = new int[m];
        int idx = 0; 
        for (int[] q : nq) {
            int x = q[0], y = q[1], i = q[2];
            // 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）
            while (idx < n && nums[idx][0] >= x) {
                add(sz - map.get(nums[idx][1]), nums[idx][0] + nums[idx][1]);
                idx++;
            }
            ans[i] = query(sz - map.get(y)); // 查询树状数组中的最值
        }
        return ans;
    }
}

C++ 代码：

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
class Solution {
public:
    int sz;
    vector<int> tr;
    int lowbit(int x) {
        return x & -x;
    }
    void add(int a, int b) {
        for (int i = a; i <= sz; i += lowbit(i)) tr[i] = max(tr[i], b);
    }
    int query(int x) {
        int ans = -1;
        for (int i = x; i > 0; i -= lowbit(i)) ans = max(ans, tr[i]);
        return ans;
    }
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        int n = nums1.size(), m = queries.size();
        // 构建新的 nums 和 nq
        vector<vector<int>> nums(n, vector<int>(2));
        vector<vector<int>> nq(m, vector<int>(3));
        for (int i = 0; i < n; i++) {
            nums[i][0] = nums1[i]; nums[i][1] = nums2[i];
        }
        for (int i = 0; i < m; i++) {
            nq[i][0] = queries[i][0]; nq[i][1] = queries[i][1]; nq[i][2] = i;
        }
        
        // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
        unordered_set<int> set;
        for (auto& x : nums) set.insert(x[1]);
        for (auto& q : nq) set.insert(q[1]);
        vector<int> list(set.begin(), set.end());
        sort(list.begin(), list.end());
        sz = list.size();
        map<int, int> map;
        for (int i = 0; i < sz; i++) map[list[i]] = i;
        
        // 调整询问顺序, 解决其中一维限制
        sort(nums.begin(), nums.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] > b[0];
        });
        sort(nq.begin(), nq.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] > b[0];
        });
        
        tr.resize(sz + 10, -1);
        
        vector<int> ans(m);
        int idx = 0;
        for (auto& q : nq) {
            int x = q[0], y = q[1], i = q[2];
            // 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）
            while (idx < n && nums[idx][0] >= x) {
                add(sz - map[nums[idx][1]], nums[idx][0] + nums[idx][1]);
                idx++;
            }
            ans[i] = query(sz - map[y]); // 查询树状数组中的最值
        }
        return ans;
    }
};

Python 代码：
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
class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        sz = 0
        tr = []

        def lowbit(x):
            return x & -x
        def add(a, b):
            i = a
            while i <= sz:
                tr[i] = max(tr[i], b)
                i += lowbit(i)
        def query(x):
            ans, i = -1, x
            while i > 0:
                ans = max(ans, tr[i])
                i -= lowbit(i)
            return ans
        
        n, m = len(nums1), len(queries)
        # 构建新的 nums 和 nq
        nums = [(nums1[i], nums2[i]) for i in range(n)]
        nq = [(queries[i][0], queries[i][1], i) for i in range(m)]
        
        #  对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
        unique_set = set()
        for x in nums:
            unique_set.add(x[1])
        for q in nq:
            unique_set.add(q[1])
        unique_list = list(unique_set)
        unique_list.sort()
        sz = len(unique_list)
        mapping = {val: idx for idx, val in enumerate(unique_list)}
        
        # 调整询问顺序, 解决其中一维限制
        nums.sort(key=lambda x: x[0], reverse=True)
        nq.sort(key=lambda x: x[0], reverse=True)
        
        tr = [-1] * (sz + 10)
        
        ans = [0] * m
        idx = 0
        for x, y, i in nq:
            # 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）
            while idx < n and nums[idx][0] >= x:
                add(sz - mapping[nums[idx][1]], nums[idx][0] + nums[idx][1])
                idx += 1
            ans[i] = query(sz - mapping[y])  # 查询树状数组中的最值
        return ans

TypeScript 代码：
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
function maximumSumQueries(nums1: number[], nums2: number[], queries: number[][]): number[] {
    let sz = 0;
    let tr = [];

    const lowbit = function(x: number): number {
        return x & -x;
    }
    const add = function(a: number, b: number): void {
        for (let i = a; i <= sz; i += lowbit(i)) tr[i] = Math.max(tr[i], b);
    }
    const query = function(x: number): number {
        let ans = -1;
        for (let i = x; i > 0; i -= lowbit(i)) ans = Math.max(ans, tr[i]);
        return ans;
    }

    const n = nums1.length, m = queries.length;
    // 构建新的 nums 和 nq
    const nums = Array.from({ length: n }, (_, i) => [nums1[i], nums2[i]]);
    const nq = Array.from({ length: m }, (_, i) => [...queries[i], i]);

    // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
    const set: Set<number> = new Set();
    for (const x of nums) set.add(x[1]);
    for (const q of nq) set.add(q[1]);
    const list: number[] = [...set];
    list.sort((a, b) => a - b);
    sz = list.length;
    const mapping = new Map();
    for (let i = 0; i < sz; i++) mapping.set(list[i], i);
        
    // 调整询问顺序, 解决其中一维限制
    nums.sort((a, b) => b[0] - a[0]);
    nq.sort((a, b) => b[0] - a[0]);

    tr = Array(sz + 10).fill(-1);
    const ans = Array(m).fill(0);
    let idx = 0;
    for (let [x, y, i] of nq) {
        // 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）
        while (idx < n && nums[idx][0] >= x) {
            add(sz - mapping.get(nums[idx][1])!, nums[idx][0] + nums[idx][1]);
            idx++;
        }
        ans[i] = query(sz - mapping.get(y)!); // 查询树状数组中的最值
    }
    return ans;
};

  • 时间复杂度：令 nums1 长度为 $n$，queries 长度为 $m$，构建 nums 和 nq 的复杂度为 $O(n + m)$；离散化复杂度为 $O((n + m) \log{(n + m)})$；对 nums 和 nq 的排序复杂度为 $O(n\log{n} + m\log{m})$；构建答案复杂度为 $O(m + n\log{n})$。整体复杂度为 $O((n + m) \log {(n + m)})$
  • 空间复杂度：$O(n + m)$

进阶

本题解讲述了「从一维到二维偏序问题」时，可通过「一维排序，一维树状数组」求通解。

那三维偏序问题呢？是否存在通用的解决思路。

答：一维排序，一维归并，一维树状数组。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2736 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。