胖蔡说技术
随便扯扯

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] >= 1nums1[j] + nums2[j] 等于 6 ,可以证明 6 是可以获得的最大值。
对于第 2 个查询:xi = 1 且 yi = 3 ,可以选择下标 j = 2 ,此时 nums1[j] >= 1 且 nums2[j] >= 3nums1[j] + nums2[j] 等于 10 ,可以证明 10 是可以获得的最大值。
对于第 3 个查询:xi = 2 且 yi = 5 ,可以选择下标 j = 3 ,此时 nums1[j] >= 2 且 nums2[j] >= 5nums1[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、先对符合条件的数值对进行存储,然后进行求值替换,提高复杂数据的运算速度

赞(0) 打赏
转载请附上原文出处链接:胖蔡叨叨叨 » Leetcode题目:最大和查询
分享到: 更多 (0)

请小编喝杯咖啡~

支付宝扫一扫打赏

微信扫一扫打赏