力扣2389-和有限的最长子序列

摘要: 一个比较综合的简单题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，本文我们来看力扣上的一道我认为不错的题目，2389. 和有限的最长子序列，本题在力扣上标记为简单题，但该题综合了排序、贪心、前缀和、二分等众多基础算法，最终代码很短，按照 【连载】面试好题 的观点，非常适合面试。

题目

• 2389. 和有限的最长子序列

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

提示：

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 1e6

示例 1：
输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：

• 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
• 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
• 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

示例 2：
输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

题解

算法：排序 + 贪心 + 前缀和 + 二分

由于我们选的是子序列，并且是考察子序列的和，因此选出的子序列的顺序不重要。因此给定了 queries[i] 之后，我们要选出的是 nums 这 n 个元素的子集，使得子集和小于 queries[i] 的前提下的元素个数最大。

下面的问题就是给定这个子集怎么选。直觉上应该从最小的开始选，假设当前要选的子集和不超过 q = queries[i]，最终选出的 k 个元素构成的子集为 $\{a_{1}, …, a_{k}\}$，其和为 s，那么 $s \leq q$ 且 nums 中剩余的元素最大为 $q - s - 1$。

如果此时 nums 中存在一个元素 x，比选出的 k 个元素中的最大的(假设为 $a_{k}$)小，也就是 $x < a_{k}$，那么把 $a_{k}$ 替换为 x，所得新子集的长度仍为 k，和为 $s - a_{k} + x$，但 nums 剩余元素中可能的最大值 $q - s - 1$ 就有可能大于 $q - s + a_{k} - x$，那么就可以将该值也选出来放到子集中，这样自己长度就增加到 k + 1。

以上是贪心正确性证明中的范围缩放法：

范围缩放法

证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。

因此先对 nums 从小到大排序，对于 q = queries[i]，然后从小到大遍历 nums，每遍历到一个 nums[i]，就将该元素累加到 sum 中，直至 sum > q 结束。

由于有 m 次查询，因此我们可以将排序后的 nums 的前缀和 sums 预处理出来，sums[i] 表示 nums[0..i-1] 的和。这样就不用每次查询都来一次遍历求和的过程了。

对于 q = queries[i]，我们只需要在 sums 中二分地找到小于等于 q 的最大值即可。

预处理的时间复杂度 $O(n\log{n})$，查询的时间复杂度 $O(m\log{n})$，总时间复杂度 $O(m+n)\log{n}$。

代码 (C++)

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> sums(n + 1);
        for(int i = 1; i <= n; ++i)
            sums[i] = sums[i - 1] + nums[i - 1];
        int m = queries.size();
        vector<int> result(m);
        for(int i = 0; i < m; ++i)
        {
            // sums 中小于等于 queries[i] 的最大值
            auto iter = upper_bound(sums.begin(), sums.end(), queries[i]);
            result[i] = iter - sums.begin() - 1;
        }
        return result;
    }
};

---