网站建设用处,wordpress邮件,杭州网站建设技术,企业网站的建设 摘要题目#xff1a;
2736. 最大和查询
给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 #xff0c;另给你一个下标从 1 开始的二维数组 queries #xff0c;其中 queries[i] [xi, yi] 。
对于第 i 个查询#xff0c;在所有满足 nums1[j] xi 且 nums2[j]…题目
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
解答 代码
class Solution {public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {int nnums1.length;int[][] sortedNumsnew int[n][2];for(int i0;in;i){sortedNums[i][0]nums1[i];sortedNums[i][1]nums2[i];}Arrays.sort(sortedNums,(a,b)-b[0]-a[0]);int qqueries.length;int[][] sortedQueriesnew int[q][3];for(int i0;iq;i){sortedQueries[i][0]i;sortedQueries[i][1]queries[i][0];sortedQueries[i][2]queries[i][1];}Arrays.sort(sortedQueries,(a,b)-b[1]-a[1]);Listint[] stacknew ArrayListint[]();int[] answernew int[q];Arrays.fill(answer,-1);int j0;for(int[] query:sortedQueries){int iquery[0],xquery[1],yquery[2];while(jnsortedNums[j][0]x){int[] pairsortedNums[j];int num1pair[0];int num2pair[1];while(!stack.isEmpty()stack.get(stack.size()-1)[1]num1num2){stack.remove(stack.size()-1);}if(stack.isEmpty()||stack.get(stack.size()-1)[0]num2){stack.add(new int[]{num2,num1num2});}j;}int kbinarySearch(stack,y);if(kstack.size()){answer[i]stack.get(k)[1];}}return answer;}public int binarySearch(Listint[] list,int target){int low0,highlist.size();while(lowhigh){int midlow(high-low)/2;if(list.get(mid)[0]target){highmid;}else{lowmid1;}}return low;}
}
结果
