LC 2736. 最大和查询

题目描述

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

给你两个长度为 n、下标从 0 开始的整数数组 nums1nums2,另给你一个下标从 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$

离散化 + 排序 + 树状数组

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

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

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

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

希望你牢牢记住:$nums[i] = [nums1[i], nums2[i]]$ 是对 nums1nums2 的简单合并;而 $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]$,同时使用变量 idxnums 进行扫描,若满足 $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$,构建 numsnq 的复杂度为 $O(n + m)$;离散化复杂度为 $O((n + m) \log{(n + m)})$;对 numsnq 的排序复杂度为 $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 原题链接和其他优选题解。