千问 LeetCode 2736. 最大和查询 Java实现

这是一道经典的离线查询 贪心 二分查找的困难题。 核心思路题目要求对于每个查询 [x, y]找出所有满足 nums1[j] x 且 nums2[j] y 的下标 j 中nums1[j] nums2[j] 的最大值。直接对每个查询暴力遍历会超时。我们可以采用离线查询的策略通过巧妙的排序和数据结构来优化1. 离线处理与排序我们将所有的查询按照 x 从大到小排序同时保留原始下标。同时将数组中的元素 (nums1[i], nums2[i]) 也按照 nums1[i] 从大到小排序。这样当我们按顺序处理每个查询时之前处理过的、满足 nums1[j] 当前查询的x 的所有元素都可以被我们利用起来。2. 单调栈维护最优解对于已经满足 nums1 条件的元素我们只需要关心它们的 nums2 和 总和(nums1nums2)。我们使用一个单调栈来维护这些候选元素。栈中的元素按照 nums2 升序排列同时对应的 总和 必须是降序的即如果一个元素的 nums2 更小但 总和 也更低那它永远不可能成为最优解直接淘汰。3. 二分查找答案对于当前的查询 y我们只需要在单调栈中通过二分查找找到第一个 nums2 y 的元素。由于栈内 总和 具有单调性找到的第一个满足条件的元素其对应的 总和 就是当前查询的最大值。 Java 实现代码import java.util.*;class Solution {public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {int n nums1.length;int m queries.length;// 1. 将 nums1 和 nums2 打包并按 nums1 降序排序int[][] pairs new int[n][2];for (int i 0; i n; i) {pairs[i] new int[]{nums1[i], nums2[i]};}Arrays.sort(pairs, (a, b) - b[0] - a[0]);// 2. 将 queries 带上原始下标并按 x 降序排序int[][] sortedQueries new int[m][3]; // [x, y, original_index]for (int i 0; i m; i) {sortedQueries[i] new int[]{queries[i][0], queries[i][1], i};}Arrays.sort(sortedQueries, (a, b) - b[0] - a[0]);int[] answer new int[m];Arrays.fill(answer, -1);// 单调栈存储 [nums2_value, sum_value]按 nums2_value 升序排列Listint[] stack new ArrayList();int j 0; // 指向 pairs 数组的指针// 3. 遍历排序后的查询for (int[] query : sortedQueries) {int x query[0];int y query[1];int idx query[2];// 将所有满足 nums1 x 的元素加入单调栈while (j n pairs[j][0] x) {int num2 pairs[j][1];int sum pairs[j][0] pairs[j][1];// 维护单调栈的性质// 如果栈顶元素的 sum 当前 sum说明栈顶元素不如当前元素优弹出while (!stack.isEmpty() stack.get(stack.size() - 1)[1] sum) {stack.remove(stack.size() - 1);}// 如果栈为空或者栈顶元素的 nums2 小于当前 nums2才加入栈// (如果栈顶 nums2 更大且 sum 也更大当前元素就没用了)if (stack.isEmpty() || stack.get(stack.size() - 1)[0] num2) {stack.add(new int[]{num2, sum});}j;}// 4. 在单调栈中二分查找第一个 nums2 y 的元素int left 0, right stack.size();while (left right) {int mid left (right - left) / 2;if (stack.get(mid)[0] y) {right mid;} else {left mid 1;}}// 如果找到了满足条件的元素更新答案if (left stack.size()) {answer[idx] stack.get(left)[1];}}return answer;}} 复杂度分析* 时间复杂度O(N log N Q log Q Q log N)。* 对 pairs 和 queries 排序分别需要 O(N log N) 和 O(Q log Q)。* 遍历查询时每个元素最多进出单调栈一次O(N)每次查询进行一次二分查找O(log N)。* 空间复杂度O(N Q)主要用于存储排序后的数组、单调栈以及结果数组。