class Solution {
public:
vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
}
};
2736. 最大和查询
给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [xi, yi] 。
对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，找出 nums1[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。
返回数组 answer ，其中 answer[i] 是第 i 个查询的答案。
示例 1：
输入：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：
输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
输出：[9,9,9]
解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。
示例 3：
输入：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 <= 1051 <= nums1[i], nums2[i] <= 109 1 <= queries.length <= 105queries[i].length == 2xi == queries[i][1]yi == queries[i][2]1 <= xi, yi <= 109原站题解
rust 解法, 执行用时: 52 ms, 内存消耗: 10.1 MB, 提交时间: 2023-11-17 16:33:25
impl Solution {
pub fn maximum_sum_queries(nums1: Vec<i32>, nums2: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
let mut a: Vec<(i32, i32)> = nums1.into_iter().zip(nums2.into_iter()).collect();
a.sort_by(|x, y| y.0.cmp(&x.0));
let mut qid: Vec<usize> = (0..queries.len()).collect();
qid.sort_by(|&i, &j| queries[j][0].cmp(&queries[i][0]));
let mut ans = vec![-1; queries.len()];
let mut st: Vec<(i32, i32)> = Vec::new();
let mut j = 0;
for &i in &qid {
let x = queries[i][0];
let y = queries[i][1];
while j < a.len() && a[j].0 >= x { // 下面只需关心 a[j].1
while !st.is_empty() && st.last().unwrap().1 <= a[j].0 + a[j].1 { // a[j].1 >= st.last().unwrap().0
st.pop();
}
if st.is_empty() || st.last().unwrap().0 < a[j].1 {
st.push((a[j].1, a[j].0 + a[j].1));
}
j += 1;
}
let p = st.partition_point(|&p| p.0 < y);
if p < st.len() {
ans[i] = st[p].1;
}
}
ans
}
}
javascript 解法, 执行用时: 484 ms, 内存消耗: 83.8 MB, 提交时间: 2023-11-17 16:33:07
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number[][]} queries
* @return {number[]}
*/
var maximumSumQueries = function (nums1, nums2, queries) {
const a = _.zip(nums1, nums2).sort((a, b) => b[0] - a[0])
const qid = [...queries.keys()].sort((i, j) => queries[j][0] - queries[i][0]);
const ans = Array(queries.length);
const st = [];
let j = 0;
for (const i of qid) {
const [x, y] = queries[i];
for (; j < a.length && a[j][0] >= x; j++) { // 下面只需关心 a[j][1]
while (st.length && st[st.length - 1][1] <= a[j][0] + a[j][1]) { // a[j][1] >= st[st.length-1][0]
st.pop();
}
if (!st.length || st[st.length - 1][0] < a[j][1]) {
st.push([a[j][1], a[j][0] + a[j][1]]);
}
}
const p = lowerBound(st, y);
ans[i] = p < st.length ? st[p][1] : -1;
}
return ans;
};
// 开区间写法，原理请看 b23.tv/AhwfbS2
var lowerBound = function (st, target) {
let left = -1, right = st.length; // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
const mid = left + ((right - left) >> 1);
if (st[mid][0] >= target) {
right = mid; // 范围缩小到 (left, mid)
} else {
left = mid; // 范围缩小到 (mid, right)
}
}
return right; // 或者 left+1
}
cpp 解法, 执行用时: 436 ms, 内存消耗: 180.8 MB, 提交时间: 2023-11-17 16:32:41
class Solution {
public:
vector<int> maximumSumQueries(vector<int> &nums1, vector<int> &nums2, vector<vector<int>> &queries) {
vector<pair<int, int>> a(nums1.size());
for (int i = 0; i < nums1.size(); i++) {
a[i] = {nums1[i], nums2[i]};
}
sort(a.begin(), a.end(),
[](auto &a, auto &b) { return a.first > b.first; });
vector<int> qid(queries.size());
iota(qid.begin(), qid.end(), 0);
sort(qid.begin(), qid.end(),
[&](int i, int j) { return queries[i][0] > queries[j][0]; });
vector<int> ans(queries.size());
vector<pair<int, int>> st;
int j = 0;
for (int i: qid) {
int x = queries[i][0], y = queries[i][1];
for (; j < a.size() && a[j].first >= x; j++) { // 下面只需关心 a[j].second
while (!st.empty() && st.back().second <= a[j].first + a[j].second) { // a[j].second >= st.back().first
st.pop_back();
}
if (st.empty() || st.back().first < a[j].second) {
st.emplace_back(a[j].second, a[j].first + a[j].second);
}
}
auto it = lower_bound(st.begin(), st.end(), y,
[](const auto &p, int val) { return p.first < val; });
ans[i] = it != st.end() ? it->second : -1;
}
return ans;
}
};
java 解法, 执行用时: 63 ms, 内存消耗: 85 MB, 提交时间: 2023-11-17 16:32:17
class Solution {
public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
int n = nums1.length;
int[][] a = new int[n][2];
for (int i = 0; i < n; i++) {
a[i][0] = nums1[i];
a[i][1] = nums2[i];
}
Arrays.sort(a, (x, y) -> y[0] - x[0]);
Integer[] qid = new Integer[queries.length];
for (int i = 0; i < queries.length; i++) {
qid[i] = i;
}
Arrays.sort(qid, (i, j) -> queries[j][0] - queries[i][0]);
int[] ans = new int[queries.length];
List<int[]> st = new ArrayList<>();
int j = 0;
for (int i : qid) {
int x = queries[i][0], y = queries[i][1];
for (; j < n && a[j][0] >= x; j++) { // 下面只需关心 a[j][1]
while (!st.isEmpty() && st.get(st.size() - 1)[1] <= a[j][0] + a[j][1]) { // a[j][1] >= st.get(st.size()-1)[0]
st.remove(st.size() - 1);
}
if (st.isEmpty() || st.get(st.size() - 1)[0] < a[j][1]) {
st.add(new int[]{a[j][1], a[j][0] + a[j][1]});
}
}
int p = lowerBound(st, y);
ans[i] = p < st.size() ? st.get(p)[1] : -1;
}
return ans;
}
// 开区间写法，原理请看 b23.tv/AhwfbS2
private int lowerBound(List<int[]> st, int target) {
int left = -1, right = st.size(); // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
int mid = (left + right) >>> 1;
if (st.get(mid)[0] >= target) {
right = mid; // 范围缩小到 (left, mid)
} else {
left = mid; // 范围缩小到 (mid, right)
}
}
return right;
}
}
golang 解法, 执行用时: 328 ms, 内存消耗: 21.8 MB, 提交时间: 2023-06-13 14:51:04
func maximumSumQueries(nums1, nums2 []int, queries [][]int) (ans []int) {
type pair struct{ x, y int }
a := make([]pair, len(nums1))
for i, x := range nums1 {
a[i] = pair{x, nums2[i]}
}
sort.Slice(a, func(i, j int) bool { return a[i].x < a[j].x })
for i := range queries {
queries[i] = append(queries[i], i)
}
sort.Slice(queries, func(i, j int) bool { return queries[i][0] > queries[j][0] })
ans = make([]int, len(queries))
st := []pair{}
i := len(a) - 1
for _, q := range queries {
for i >= 0 && a[i].x >= q[0] {
for len(st) > 0 && st[len(st)-1].y <= a[i].x+a[i].y {
st = st[:len(st)-1] // a[i].y >= st[len(st)-1].x
}
if len(st) == 0 || st[len(st)-1].x < a[i].y {
st = append(st, pair{a[i].y, a[i].x + a[i].y})
}
i--
}
j := sort.Search(len(st), func(i int) bool { return st[i].x >= q[1] })
if j < len(st) {
ans[q[2]] = st[j].y
} else {
ans[q[2]] = -1
}
}
return ans
}
python3 解法, 执行用时: 328 ms, 内存消耗: 65.1 MB, 提交时间: 2023-06-13 14:50:45
# 排序 + 单调栈上二分
class Solution:
def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
ans = [-1] * len(queries)
st = []
a = sorted((a, b) for a, b in zip(nums1, nums2))
i = len(a) - 1
for qid, (x, y) in sorted(enumerate(queries), key=lambda p: -p[1][0]):
while i >= 0 and a[i][0] >= x:
ax, ay = a[i]
while st and st[-1][1] <= ax + ay: # ay >= st[-1][0]
st.pop()
if not st or st[-1][0] < ay:
st.append((ay, ax + ay))
i -= 1
j = bisect_left(st, (y,))
if j < len(st):
ans[qid] = st[j][1]
return ans