2736. 最大和查询 (opens new window)

1.二分+单调栈

将nums1和nums2合并，并进行预处理。预处理分为两个步骤：

• 将数组按照nums1元素降序排序
• 将查询数组queries按照第一个元素(对应nums1限制条件)降序排序。

对于每个查询，将nums当中符合nums1约束的数对加入单调栈当中，而前面排过序，保证单调栈的数对中nums1是递减的。然后再对栈进行二分，找到满足nums2约束的数对。

对于每次查询，假设前一个元素是a,b，下一个满足nums1约束的数对是c,d。因为前面预处理所以有a>c，那么数对（c,d）的入栈情况可以分为以下几种情况讨论：

• 如果当前b>=d，那么后续查询当中(a,b)比(c,d)更有资格成为最大和查询的结果。因此入栈的元素一定满足nums2[y]<nums2[y']，即自栈底到栈顶nums2是递增的。
• 排除掉栈中的无效元素：如果c+d>a+b，那么后续的查询当中，(c,d)数对更有资格成为最大和查询，因为查询也是按照queries[0]降序排序的，因此如果有c>=x，那么后续查询中也一定有c>=x'。因此入栈前，只要栈顶数对和小于当前数对和则需要出栈，维护单调栈中数对和是递减的。

最终，维护的单调栈自底至栈顶，nums1递减，nums2递增，nums1+nums2递减。最后使用二分找到最小满足nums2<y的数对，即为最大和。

💡启发：多维数组的单调约束问题，不一定需要同时对多个维度进行排序，可以先对其中一个维度排序入手，再使用数据结构对元素进行筛选过滤。

class Solution {
    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int[] res = new int[queries.length];
        int[][] nums = new int[nums1.length][2];
        for (int i = 0; i < nums1.length; i++) {
            nums[i][0] = nums1[i];
            nums[i][1] = nums2[i];
        }
        Arrays.sort(nums, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        });

        Integer[] queriesInx = new Integer[queries.length];
        for (int i = 0; i < queries.length; i++) {
            queriesInx[i] = i;
        }
        Arrays.sort(queriesInx, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return queries[o2][0] - queries[o1][0];
            }
        });
        
        List<int[]> stack = new ArrayList<>();
        int nums1Inx=0;
        for (int i = 0; i < queries.length; i++) {
            int x = queries[queriesInx[i]][0];
            int y = queries[queriesInx[i]][1];
            //找出满足nums1>=x的元素
            for (; nums1Inx < nums1.length && nums[nums1Inx][0] >= x; nums1Inx++) {
                int tmpx = nums[nums1Inx][0];
                int tmpy = nums[nums1Inx][1];
                //维护单调栈元素：自栈底到栈顶依次是：nums1递减，nums2递增，（nums1+nums2）递减
                while (!stack.isEmpty()) {
                    int[] tail = stack.get(stack.size() - 1);
                    if(tail[0]+tail[1]<=tmpx+tmpy) stack.remove(stack.size() - 1);
                    else break;
                }
                 if(stack.isEmpty()||stack.get(stack.size()-1)[1]<tmpy) stack.add(nums[nums1Inx]);
            }
            //二分
            int ansInx = stack.size()==0?-1:lowhigh(stack, y);
            res[queriesInx[i]] = ansInx == -1 ? -1 : stack.get(ansInx)[0] + stack.get(ansInx)[1];

        }
        return res;
    }

    public int lowhigh(List<int[]> stack, int y) {
        int low = 0, high = stack.size() - 1;
        while (low < high) {
            int mid = (low + high) >> 1;
            if(stack.get(mid)[1]<y) low = mid + 1;
            else high = mid;
        }
        return stack.get(low)[1]>=y?low:-1;
    }
}