likes
comments
collection
share

2736. 最大和查询 : 从一维限制到二维限制，逐步思考剖析本题（进阶一问）

作者站长头像
站长
· 阅读数 5

题目描述

这是 LeetCode 上的 2736. 最大和查询 ，难度为 困难。

Tag : 「排序」、「离散化」、「树状数组」

给你两个长度为 n、下标从 0 开始的整数数组 nums1 和 nums2，另给你一个下标从 1 开始的二维数组 queries，其中 queries[i]=[xi,yi]queries[i] = [x_{i}, y_{i}]queries[i]=[xi​,yi​] 。

对于第 i 个查询，在所有满足 nums1[j]>=xinums1[j] >= x_{i}nums1[j]>=xi​ 且 nums2[j]>=yinums2[j] >= y_{i}nums2[j]>=yi​ 的下标 j (0<=j<n0 <= j < n0<=j<n) 中，找出 nums1[j]+nums2[j]nums1[j] + nums2[j]nums1[j]+nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 −1-1−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.lengthnums1.length = nums2.lengthnums1.length=nums2.length
  • n=nums1.lengthn = nums1.lengthn=nums1.length
  • 1<=n<=1051 <= n <= 10^51<=n<=105
  • 1<=nums1[i],nums2[i]<=1091 <= nums1[i], nums2[i] <= 10^91<=nums1[i],nums2[i]<=109
  • 1<=queries.length<=1051 <= queries.length <= 10^51<=queries.length<=105
  • queries[i].length=2queries[i].length = 2queries[i].length=2
  • xi=queries[i][1]x_{i} = queries[i][1]xi​=queries[i][1]
  • yi=queries[i][2]y_{i} = queries[i][2]yi​=queries[i][2]
  • 1<=xi,yi<=1091 <= x_{i}, y_{i} <= 10^91<=xi​,yi​<=109

离散化 + 排序 + 树状数组

根据题意，两个等长的数组 num1 和 nums2，只能是相同下标的元素凑成一对。

我们不妨用两个一维数组 nums1 和 nums2 构建出一个二维数组 nums，方便后续处理，其中 nums[i]=[nums1[i],nums2[i]]nums[i] = [nums1[i], nums2[i]]nums[i]=[nums1[i],nums2[i]]。

同时对 queries 进行简单拓展，构建新的二维数组 nq，目的是对原有下标信息进行记录，其中 nq[i]=[queries[i][0],queries[i][1],i]nq[i] = [queries[i][0], queries[i][1], i]nq[i]=[queries[i][0],queries[i][1],i]（此处构建新 nq 的作用，下文会说）。

好了，现在我们有两个新的数组 nums 和 nq，接下来所有讨论都会针对新数组进行。

我希望你牢牢记住：nums[i]=[nums1[i],nums2[i]]nums[i] = [nums1[i], nums2[i]]nums[i]=[nums1[i],nums2[i]] 是对 nums1 和 nums2 的简单合并；而 nq[i]=[queries[i][0],queries[i][1],i]nq[i] = [queries[i][0], queries[i][1], i]nq[i]=[queries[i][0],queries[i][1],i] 是对 queries 原有下标的拓展记录。

做完简单的预处理工作后，来思考一个前置问题：

假设其他内容不变，要求从满足「nums[j][0]≥nq[i][0]nums[j][0] \geq nq[i][0]nums[j][0]≥nq[i][0] 且 nums[j][1]≥nq[i][1]nums[j][1] \geq nq[i][1]nums[j][1]≥nq[i][1]」调整为仅需满足「nums[j][0]≥nq[i][0]nums[j][0] \geq nq[i][0]nums[j][0]≥nq[i][0]」，我们会如何求解？

一个简单的做法：

  1. 对 nums 中的第一维（即 nums[i][0]=nums1[i]nums[i][0] = nums1[i]nums[i][0]=nums1[i]）和 nq 中第一维（即 nq[i][0]=queries[i][0]=xinq[i][0] = queries[i][0] = x_{i}nq[i][0]=queries[i][0]=xi​）排倒序；

  2. 从前往后处理每个询问 nq[i]nq[i]nq[i]，同时使用变量 idx 对 nums 进行扫描，若满足 nums[idx][0]≥nq[i][0]nums[idx][0] \geq nq[i][0]nums[idx][0]≥nq[i][0] 时，将 idx 右移，同时记录已被扫描的数对和 nums[idx′][0]+nums[idx′][1]nums[idx'][0] + nums[idx'][1]nums[idx′][0]+nums[idx′][1] 。

    当 idx 不能再后移时，说明当前所有满足 nums[idx][0]≥nq[i][0]nums[idx][0] \geq nq[i][0]nums[idx][0]≥nq[i][0] 要求的数对已被扫描完，在记录的数对和中取最大值，即是当前询问 nq[i]nq[i]nq[i] 的答案 ans[nq[i][2]]ans[nq[i][2]]ans[nq[i][2]]（此处解释了为什么需要构造新数组 nq，因为询问处理是按照排序后进行，但在 ans 中需要映射回原有顺序）。

  3. 重复步骤 222，直到处理完所有询问。

搞定前置问题后，回到原问题，需要满足「nums[j][0]≥nq[i][0]nums[j][0] \geq nq[i][0]nums[j][0]≥nq[i][0] 且 nums[j][1]≥nq[i][1]nums[j][1] \geq nq[i][1]nums[j][1]≥nq[i][1]」要求。

进一步思考，排序 + 调整询问顺序，只能解决其中一维限制要求，另一维该如何处理？

或者更加直接的问题：如何在被记录的所有数对和 nums[idx′][0]+nums[idx′][1]nums[idx'][0] + nums[idx'][1]nums[idx′][0]+nums[idx′][1] 中找出那些满足 nums[j][1]≥nq[i][1]nums[j][1] \geq nq[i][1]nums[j][1]≥nq[i][1] 的最大数对和。

不失一般性，假设当前处理到的是 nums[idx]nums[idx]nums[idx]，其中 nums[idx][0]nums[idx][0]nums[idx][0] 的限制要求，通过前置问题的排序方式解决了。另外的 nums[idx][1]nums[idx][1]nums[idx][1] 我们希望作为“位置信息”，数对和 sum=nums[idx][0]+nums[idx][1]sum = nums[idx][0] + nums[idx][1]sum=nums[idx][0]+nums[idx][1] 作为“值信息”进行记录。

由于条件 1≤xi,yi≤1e91 \leq x_{i}, y_{i} \leq 1e91≤xi​,yi​≤1e9，我们需要对将要作为“位置信息”添加到树状数组的 nums[idx][1]nums[idx][1]nums[idx][1] 和 nq[i][1]nq[i][1]nq[i][1] 进行离散化，将其映射到 [0,m−1][0, m - 1][0,m−1] 范围内。

对于每个询问，都需要找到已遍历过的大于 nq[i][1]nq[i][1]nq[i][1] 的位置上的最大值，把离散化后的值域换成数组坐标，相当于求后缀最大值，后缀最大值可通过相反数，变成求前缀最大值。

能够实现类似的前缀操作，支持“单点修改”和“区间查询”的数据结构是「树状数组」。

Java 代码：

class Solution {
    int sz;
    int[] tr;
    int lowbit(int x) {
        return x & -x;
    }
    void add(int a, int b) {
        for (int i = a; i <= sz; i += lowbit(i)) tr[i] = Math.max(tr[i], b);
    }
    int query(int x) {
        int ans = -1;
        for (int i = x; i > 0; i -= lowbit(i)) ans = Math.max(ans, tr[i]);
        return ans;
    }
    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length, m = queries.length;
        // 构建新的 nums 和 nq
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; i++) nums[i] = new int[]{nums1[i], nums2[i]};
        int[][] nq = new int[m][3];
        for (int i = 0; i < m; i++) nq[i] = new int[]{queries[i][0], queries[i][1], i};

        // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
        Set<Integer> set = new HashSet<>();
        for (int[] x : nums) set.add(x[1]);
        for (int[] q : nq) set.add(q[1]);
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        sz = list.size();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sz; i++) map.put(list.get(i), i);

        // 调整询问顺序, 解决其中一维限制
        Arrays.sort(nums, (a,b)->b[0]-a[0]);
        Arrays.sort(nq, (a,b)->b[0]-a[0]);

        tr = new int[sz + 10];
        Arrays.fill(tr, -1);

        int[] ans = new int[m];
        int idx = 0; 
        for (int[] q : nq) {
            int x = q[0], y = q[1], i = q[2];
            // 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）
            while (idx < n && nums[idx][0] >= x) {
                add(sz - map.get(nums[idx][1]), nums[idx][0] + nums[idx][1]);
                idx++;
            }
            ans[i] = query(sz - map.get(y)); // 查询树状数组中的最值
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int sz;
    vector<int> tr;
    int lowbit(int x) {
        return x & -x;
    }
    void add(int a, int b) {
        for (int i = a; i <= sz; i += lowbit(i)) tr[i] = max(tr[i], b);
    }
    int query(int x) {
        int ans = -1;
        for (int i = x; i > 0; i -= lowbit(i)) ans = max(ans, tr[i]);
        return ans;
    }
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        int n = nums1.size(), m = queries.size();
        // 构建新的 nums 和 nq
        vector<vector<int>> nums(n, vector<int>(2));
        vector<vector<int>> nq(m, vector<int>(3));
        for (int i = 0; i < n; i++) {
            nums[i][0] = nums1[i]; nums[i][1] = nums2[i];
        }
        for (int i = 0; i < m; i++) {
            nq[i][0] = queries[i][0]; nq[i][1] = queries[i][1]; nq[i][2] = i;
        }
        
        // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
        unordered_set<int> set;
        for (auto& x : nums) set.insert(x[1]);
        for (auto& q : nq) set.insert(q[1]);
        vector<int> list(set.begin(), set.end());
        sort(list.begin(), list.end());
        sz = list.size();
        map<int, int> map;
        for (int i = 0; i < sz; i++) map[list[i]] = i;
        
        // 调整询问顺序, 解决其中一维限制
        sort(nums.begin(), nums.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] > b[0];
        });
        sort(nq.begin(), nq.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] > b[0];
        });
        
        tr.resize(sz + 10, -1);
        
        vector<int> ans(m);
        int idx = 0;
        for (auto& q : nq) {
            int x = q[0], y = q[1], i = q[2];
            // 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）
            while (idx < n && nums[idx][0] >= x) {
                add(sz - map[nums[idx][1]], nums[idx][0] + nums[idx][1]);
                idx++;
            }
            ans[i] = query(sz - map[y]); // 查询树状数组中的最值
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        sz = 0
        tr = []

        def lowbit(x):
            return x & -x
        def add(a, b):
            i = a
            while i <= sz:
                tr[i] = max(tr[i], b)
                i += lowbit(i)
        def query(x):
            ans, i = -1, x
            while i > 0:
                ans = max(ans, tr[i])
                i -= lowbit(i)
            return ans
        
        n, m = len(nums1), len(queries)
        # 构建新的 nums 和 nq
        nums = [(nums1[i], nums2[i]) for i in range(n)]
        nq = [(queries[i][0], queries[i][1], i) for i in range(m)]
        
        #  对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
        unique_set = set()
        for x in nums:
            unique_set.add(x[1])
        for q in nq:
            unique_set.add(q[1])
        unique_list = list(unique_set)
        unique_list.sort()
        sz = len(unique_list)
        mapping = {val: idx for idx, val in enumerate(unique_list)}
        
        # 调整询问顺序, 解决其中一维限制
        nums.sort(key=lambda x: x[0], reverse=True)
        nq.sort(key=lambda x: x[0], reverse=True)
        
        tr = [-1] * (sz + 10)
        
        ans = [0] * m
        idx = 0
        for x, y, i in nq:
            # 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）
            while idx < n and nums[idx][0] >= x:
                add(sz - mapping[nums[idx][1]], nums[idx][0] + nums[idx][1])
                idx += 1
            ans[i] = query(sz - mapping[y])  # 查询树状数组中的最值
        return ans

TypeScript 代码：

function maximumSumQueries(nums1: number[], nums2: number[], queries: number[][]): number[] {
    let sz = 0;
    let tr = [];

    const lowbit = function(x: number): number {
        return x & -x;
    }
    const add = function(a: number, b: number): void {
        for (let i = a; i <= sz; i += lowbit(i)) tr[i] = Math.max(tr[i], b);
    }
    const query = function(x: number): number {
        let ans = -1;
        for (let i = x; i > 0; i -= lowbit(i)) ans = Math.max(ans, tr[i]);
        return ans;
    }

    const n = nums1.length, m = queries.length;
    // 构建新的 nums 和 nq
    const nums = Array.from({ length: n }, (_, i) => [nums1[i], nums2[i]]);
    const nq = Array.from({ length: m }, (_, i) => [...queries[i], i]);

    // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
    const set: Set<number> = new Set();
    for (const x of nums) set.add(x[1]);
    for (const q of nq) set.add(q[1]);
    const list: number[] = [...set];
    list.sort((a, b) => a - b);
    sz = list.length;
    const mapping = new Map();
    for (let i = 0; i < sz; i++) mapping.set(list[i], i);
        
    // 调整询问顺序, 解决其中一维限制
    nums.sort((a, b) => b[0] - a[0]);
    nq.sort((a, b) => b[0] - a[0]);

    tr = Array(sz + 10).fill(-1);
    const ans = Array(m).fill(0);
    let idx = 0;
    for (let [x, y, i] of nq) {
        // 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）
        while (idx < n && nums[idx][0] >= x) {
            add(sz - mapping.get(nums[idx][1])!, nums[idx][0] + nums[idx][1]);
            idx++;
        }
        ans[i] = query(sz - mapping.get(y)!); // 查询树状数组中的最值
    }
    return ans;
};
  • 时间复杂度：令 nums1 长度为 nnn，queries 长度为 mmm，构建 nums 和 nq 的复杂度为 O(n+m)O(n + m)O(n+m)；离散化复杂度为 O((n+m)log⁡(n+m))O((n + m) \log{(n + m)})O((n+m)log(n+m))；对 nums 和 nq 的排序复杂度为 O(nlog⁡n+mlog⁡m)O(n\log{n} + m\log{m})O(nlogn+mlogm)；构建答案复杂度为 O(m+nlog⁡n)O(m + n\log{n})O(m+nlogn)。整体复杂度为 O((n+m)log⁡(n+m))O((n + m) \log {(n + m)})O((n+m)log(n+m))
  • 空间复杂度：O(n+m)O(n + m)O(n+m)

进阶

本题解讲述了「从一维到二维偏序问题」时，可通过「一维排序，一维树状数组」求通解。

那三维偏序问题呢？是否存在通用的解决思路。

答：一维排序，一维归并，一维树状数组。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2736 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉