Hard

题目描述

给你两个长度为 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，这是能得到的最大值。
第 2 个查询：xi = 1, yi = 3，可以选择下标 j = 2，因为 nums1[j] >= 1 且 nums2[j] >= 3。nums1[j] + nums2[j] = 10，这是能得到的最大值。
第 3 个查询：xi = 2, yi = 5，可以选择下标 j = 3，因为 nums1[j] >= 2 且 nums2[j] >= 5。nums1[j] + nums2[j] = 7，这是能得到的最大值。

示例 2：

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

示例 3：

输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
输出：[-1]

提示：

  • 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
  • 1 <= xi, yi <= 10^9

解题思路

这是一个复杂的二维查询问题，关键在于如何高效处理大量查询。

核心思路：

  1. 排序预处理：将数据点 (nums1[i], nums2[i]) 按 nums1 降序排序，将查询按 xi 降序排序（记录原始索引）
  2. 单调栈优化：使用单调栈维护有效的 (nums2[i], sum) 对，其中 sum = nums1[i] + nums2[i]
  3. 动态维护：对于每个查询 (xi, yi)，先将所有满足 nums1[j] >= xi 的点加入单调栈，然后查询满足 nums2[j] >= yi 的最大和

单调栈的作用：

  • 栈中存储 (y值, 对应的sum)，按 y 值递增，sum 值递减
  • 当插入新点时，移除所有 y 值更小但 sum 不超过新点的无用点
  • 这样保证了：对于任意 y 阈值，第一个满足条件的点就是最优解

查询过程：

  • 使用二分搜索在单调栈中找到第一个 y >= yi 的点
  • 由于单调性，该点对应的 sum 就是最大值

时间复杂度主要来自排序和单调栈操作，整体为 O((n + q) log n)，其中 n 是数组长度，q 是查询数量。

代码实现

class Solution {
public:
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        int n = nums1.size();
        vector<pair<int, int>> points(n);
        for (int i = 0; i < n; i++) {
            points[i] = {nums1[i], nums2[i]};
        }
        sort(points.begin(), points.end(), greater<pair<int, int>>());
        
        int m = queries.size();
        vector<pair<pair<int, int>, int>> sortedQueries(m);
        for (int i = 0; i < m; i++) {
            sortedQueries[i] = {{queries[i][0], queries[i][1]}, i};
        }
        sort(sortedQueries.begin(), sortedQueries.end(), greater<pair<pair<int, int>, int>>());
        
        vector<int> result(m);
        vector<pair<int, int>> stack; // (y, sum)
        int j = 0;
        
        for (auto& query : sortedQueries) {
            int x = query.first.first;
            int y = query.first.second;
            int idx = query.second;
            
            // Add all points with nums1[i] >= x
            while (j < n && points[j].first >= x) {
                int py = points[j].second;
                int sum = points[j].first + points[j].second;
                
                // Remove dominated points
                while (!stack.empty() && stack.back().second <= sum) {
                    stack.pop_back();
                }
                
                // Add current point if it's not dominated
                if (stack.empty() || stack.back().first < py) {
                    stack.push_back({py, sum});
                }
                j++;
            }
            
            // Binary search for the answer
            auto it = lower_bound(stack.begin(), stack.end(), make_pair(y, 0));
            result[idx] = (it == stack.end()) ? -1 : it->second;
        }
        
        return result;
    }
};

class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums1)
        points = [(nums1[i], nums2[i]) for i in range(n)]
        points.sort(reverse=True)
        
        m = len(queries)
        sorted_queries = [((queries[i][0], queries[i][1]), i) for i in range(m)]
        sorted_queries.sort(reverse=True)
        
        result = [0] * m
        stack = []  # (y, sum)
        j = 0
        
        for (x, y), idx in sorted_queries:
            # Add all points with nums1[i] >= x
            while j < n and points[j][0] >= x:
                px, py = points[j]
                sum_val = px + py
                
                # Remove dominated points
                while stack and stack[-1][1] <= sum_val:
                    stack.pop()
                
                # Add current point if it's not dominated
                if not stack or stack[-1][0] < py:
                    stack.append((py, sum_val))
                j += 1
            
            # Binary search for the answer
            left, right = 0, len(stack)
            while left < right:
                mid = (left + right) // 2
                if stack[mid][0] >= y:
                    right = mid
                else:
                    left = mid + 1
            
            result[idx] = stack[left][1] if left < len(stack) else -1
        
        return result

public class Solution {
    public int[] MaximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.Length;
        var points = new (int, int)[n];
        for (int i = 0; i < n; i++) {
            points[i] = (nums1[i], nums2[i]);
        }
        Array.Sort(points, (a, b) => b.Item1.CompareTo(a.Item1));
        
        int m = queries.Length;
        var sortedQueries = new ((int, int), int)[m];
        for (int i = 0; i < m; i++) {
            sortedQueries[i] = ((queries[i][0], queries[i][1]), i);
        }
        Array.Sort(sortedQueries, (a, b) => b.Item1.Item1.CompareTo(a.Item1.Item1));
        
        var result = new int[m];
        var stack = new List<(int, int)>(); // (y, sum)
        int j = 0;
        
        foreach (var query in sortedQueries) {
            int x = query.Item1.Item1;
            int y = query.Item1.Item2;
            int idx = query.Item2;
            
            // Add all points with nums1[i] >= x
            while (j < n && points[j].Item1 >= x) {
                int py = points[j].Item2;
                int sum = points[j].Item1 + points[j].Item2;
                
                // Remove dominated points
                while (stack.Count > 0 && stack[stack.Count - 1].Item2 <= sum) {
                    stack.RemoveAt(stack.Count - 1);
                }
                
                // Add current point if it's not dominated
                if (stack.Count == 0 || stack[stack.Count - 1].Item1 < py) {
                    stack.Add((py, sum));
                }
                j++;
            }
            
            // Binary search for the answer
            int left = 0, right = stack.Count;
            while (left < right) {
                int mid = (left + right) / 2;
                if (stack[mid].Item1 >= y) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            
            result[idx] = left < stack.Count ? stack[left].Item2 : -1;
        }
        
        return result;
    }
}

var maximumSumQueries = function(nums1, nums2, queries) {
    const n = nums1.length;
    const points = [];
    
    for (let i = 0; i < n; i++) {
        points.push([nums1[i], nums2[i], nums1[i] + nums2[i]]);
    }
    
    points.sort((a, b) => b[0] - a[0]);
    
    const result = [];
    
    for (const [x, y] of queries) {
        let maxSum = -1;
        
        for (const [a, b, sum] of points) {
            if (a < x) break;
            if (b >= y) {
                maxSum = Math.max(maxSum, sum);
            }
        }
        
        result.push(maxSum);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O((n + q) log n)
空间复杂度O(n + q)

其中 n 为数组长度，q 为查询数量。时间复杂度主要来自排序 O(n log n + q log q) 和单调栈操作 O(n + q log n)。

相关题目