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]$」,如何求解?
一个简单的做法:
对
nums
中的第一维(即 $nums[i][0] = nums1[i]$)和nq
中第一维(即 $nq[i][0] = queries[i][0] = x_{i}$)排倒序;从前往后处理每个询问 $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
中需要映射回原有顺序)。重复步骤 $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 |
|
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
61class 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
50class 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
48function 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 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!