Leetcode题目：最大和查询

题目描述

给你两个长度为 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 <= 105
• 1 <= nums1[i], nums2[i] <= 109 
• 1 <= queries.length <= 105
• queries[i].length == 2
• xi == queries[i][1]
• yi == queries[i][2]
• 1 <= xi, yi <= 109

实现

function maximumSumQueries(nums1: number[], nums2: number[], queries: number[][]): number[] {
    let result: number[] = Array(queries.length).fill(-1)

    let minSum = null
    let minX = null
    let minY = null
    let minEnd = null
    let maxEnd = null
    for(let j=0;j< queries.length;j++){
        const x = queries[j][0]
        const y = queries[j][1]
        const sum = x + y
        const mix = Math.max(x, y)
        if(j === 0) {
            minX = x
            minY = y
            minSum = sum
            minEnd = mix
            // maxEnd = mix
        }else {
            minSum = Math.min(minSum, sum)
            minX = Math.min(minX, x)
            minY = Math.min(minY,y)
            minEnd = Math.min(minEnd, mix)
            maxEnd = Math.max(maxEnd, mix)
        }
    }
    const length = nums1.length
    let indexArray: any[] = []

    for(let i=0;i< length;i++) {
        const n1 = nums1[i]
        const n2 = nums2[i]
        const sum = n1+n2
        const mix = Math.max(n1 , n2)
        if(n1 >= minX && n2 >= minY && sum >= minSum && mix >= minEnd) {
            let isInserted = false
            let array = [...indexArray]
            indexArray = []
            array.forEach((item: any, _index:number) => {
                if(item) {
                  if(sum > item.sum &&  (n1 >= item.n1 && n2 >= item.n2)) {
                    if(!isInserted) {
                        const model = {index:i,n1,n2,sum}
                         indexArray.push(model)
                        isInserted = true
                    }
                  }else{
                     indexArray.push(item)
                  }
                }
            })
            if(!isInserted){
                 indexArray.push({index:i,n1,n2,sum})
            }
               
        }
    }

    indexArray.forEach((item: any) => {
        const { n1,n2,sum} = item
        for(let j=0;j < queries.length;j++){
            const x = queries[j][0]
            const y = queries[j][1]
            if(n1 >= x && n2 >= y && (result[j] == -1 || sum > result[j]  ) ) {
                result[j] = sum
            }
        }
    })
    
    return result
};

解题思路

1、最大和查询，根据题意可知符合题意的最小和queries[i] = [xi, yi]，应满足 sum >= xi + yi

2、需要过滤多解的数据，并取其最大值

3、先对符合条件的数值对进行存储，然后进行求值替换，提高复杂数据的运算速度