贪心题目：和有限的最长子序列

题目

标题和出处

标题：和有限的最长子序列

出处：2389. 和有限的最长子序列

难度

2 级

题目描述

要求

给定一个长度为n \texttt{n}n的整数数组nums \texttt{nums}nums和一个长度为m \texttt{m}m的整数数组queries \texttt{queries}queries。

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

子序列是由一个数组删除某些元素或不删除元素且不改变剩余元素顺序得到的数组。

示例

示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21] \texttt{nums = [4,5,2,1], queries = [3,10,21]}nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4] \texttt{[2,3,4]}[2,3,4]
解释：查询的回答如下：

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

示例 2：

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

数据范围

• n = nums.length \texttt{n} = \texttt{nums.length}n=nums.length
• m = queries.length \texttt{m} = \texttt{queries.length}m=queries.length
• 1 ≤ n, m ≤ 1000 \texttt{1} \le \texttt{n, m} \le \texttt{1000}1≤n, m≤1000
• 1 ≤ nums[i], queries[i] ≤ 10 6 \texttt{1} \le \texttt{nums[i], queries[i]} \le \texttt{10}^\texttt{6}1≤nums[i], queries[i]≤106

解法一

思路和算法

这道题要求对于每个查询找到数组nums \textit{nums}nums中的元素之和小于等于查询值的最大元素个数。数组中的元素都是正整数，在元素综合不超过查询值的情况下，为了使元素个数最多，应选取最小的元素，理由如下。

用query \textit{query}query表示查询值。假设选取最小的元素时，最多可以选取size \textit{size}size个元素，元素之和为sum \textit{sum}sum，则sum ≤ query \textit{sum} \le \textit{query}sum≤query，且再多选取任意一个元素都会使元素之和超过query \textit{query}query。用sum ′ \textit{sum}'sum′表示最小的size + 1 \textit{size} + 1size+1个元素之和，则sum ′ > query \textit{sum}' > \textit{query}sum′>query。

将最小的size + 1 \textit{size} + 1size+1个元素中的任意一个元素替换成更大的元素，替换之后的size + 1 \textit{size} + 1size+1个元素之和大于sum ′ \textit{sum}'sum′，因此大于query \textit{query}query。因此不可能选取size + 1 \textit{size} + 1size+1个元素使元素之和不超过query \textit{query}query，该查询的答案为size \textit{size}size。

根据上述分析，可以使用贪心的思想计算每个查询的答案。

由于元素之和与元素顺序无关，因此可以将数组nums \textit{nums}nums按升序排序，然后对于每个查询，找到nums \textit{nums}nums的元素之和小于等于查询值的最长前缀，该前缀长度即为查询的答案。

代码

classSolution{publicint[]answerQueries(int[]nums,int[]queries){Arrays.sort(nums);intn=nums.length,m=queries.length;int[]answer=newint[m];for(inti=0;i<m;i++){intquery=queries[i];intsize=0;intsum=0;for(intj=0;j<n;j++){if(sum+nums[j]>query){break;}sum+=nums[j];size++;}answer[i]=size;}returnanswer;}}

复杂度分析

• 时间复杂度：O ( n log ⁡ n + n m ) O(n \log n + nm)O(nlogn+nm)，其中n nn是数组nums \textit{nums}nums的长度，m mm是数组queries \textit{queries}queries的长度。排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间，有m mm个查询，每个查询需要O ( n ) O(n)O(n)的时间，因此时间复杂度是O ( n log ⁡ n + n m ) O(n \log n + nm)O(nlogn+nm)。

• 空间复杂度：O ( log ⁡ n ) O(\log n)O(logn)，其中n nn是数组nums \textit{nums}nums的长度。排序需要O ( log ⁡ n ) O(\log n)O(logn)的递归调用栈空间。注意返回值不计入空间复杂度。

解法二

思路和算法

将数组nums \textit{nums}nums按升序排序之后，由于每次查询都需要找到nums \textit{nums}nums的元素之和小于等于查询值的最长前缀，且元素都是正整数，因此nums \textit{nums}nums的前缀和数组为单调递增，可以在前缀和数组中使用二分查找得到每个查询的答案。

创建长度为n + 1 n + 1n+1的前缀和数组prefixSums \textit{prefixSums}prefixSums，其中prefixSums [ 0 ] = 0 \textit{prefixSums}[0] = 0prefixSums[0]=0，对于0 ≤ i < n 0 \le i < n0≤i<n有prefixSums [ i + 1 ] = prefixSums [ i ] + nums [ i ] \textit{prefixSums}[i + 1] = \textit{prefixSums}[i] + \textit{nums}[i]prefixSums[i+1]=prefixSums[i]+nums[i]（此时nums \textit{nums}nums已经按升序排序），即prefixSums [ i ] \textit{prefixSums}[i]prefixSums[i]表示nums \textit{nums}nums的长度为i ii的前缀的元素之和。对于查询值query \textit{query}query，找到满足prefixSums [ index ] ≤ query \textit{prefixSums}[\textit{index}] \le \textit{query}prefixSums[index]≤query的最大下标index \textit{index}index，则查询的答案为index \textit{index}index。

代码

classSolution{publicint[]answerQueries(int[]nums,int[]queries){Arrays.sort(nums);intn=nums.length,m=queries.length;int[]prefixSums=newint[n+1];for(inti=0;i<n;i++){prefixSums[i+1]=prefixSums[i]+nums[i];}int[]answer=newint[m];for(inti=0;i<m;i++){answer[i]=binarySearch(prefixSums,queries[i]);}returnanswer;}publicintbinarySearch(int[]prefixSums,inttarget){intlow=-1,high=prefixSums.length-1;while(low<high){intmid=low+(high-low+1)/2;if(prefixSums[mid]<=target){low=mid;}else{high=mid-1;}}returnlow;}}

复杂度分析

• 时间复杂度：O ( n log ⁡ n + m log ⁡ n ) O(n \log n + m \log n)O(nlogn+mlogn)，其中n nn是数组nums \textit{nums}nums的长度，m mm是数组queries \textit{queries}queries的长度。排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间，计算前缀和数组需要O ( n ) O(n)O(n)的时间，有m mm个查询，每个查询使用二分查找需要O ( log ⁡ n ) O(\log n)O(logn)的时间，因此时间复杂度是O ( n log ⁡ n + m log ⁡ n ) O(n \log n + m \log n)O(nlogn+mlogn)。

• 空间复杂度：O ( n ) O(n)O(n)，其中n nn是数组nums \textit{nums}nums的长度。排序需要O ( log ⁡ n ) O(\log n)O(logn)的递归调用栈空间，排序后需要创建长度为n + 1 n + 1n+1的前缀和数组，因此空间复杂度是O ( n ) O(n)O(n)。注意返回值不计入空间复杂度。