贪心题目：非递增顺序的最小子序列

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题非递增顺序的最小子序列出处1403. 非递增顺序的最小子序列难度2 级题目描述要求给定一个数组nums \texttt{nums}nums要求从中抽取一个子序列满足该子序列的元素之和严格大于未包含在该子序列中的各元素之和。如果存在多个解决方案只需返回长度最小的子序列。如果仍然有多个解决方案则返回元素之和最大的子序列。数组的子序列可以通过从数组中删除一些元素也可以不删除得到。保证满足所有约束条件的解决方案是唯一的。返回的答案应当按非递增顺序排列。示例示例 1输入nums [4,3,10,9,8] \texttt{nums [4,3,10,9,8]}nums [4,3,10,9,8]输出[10,9] \texttt{[10,9]}[10,9]解释子序列[10,9] \texttt{[10,9]}[10,9]和[10,8] \texttt{[10,8]}[10,8]是满足元素之和大于其他各元素之和的最小子序列。但是[10,9] \texttt{[10,9]}[10,9]的元素之和最大。示例 2输入nums [4,4,7,6,7] \texttt{nums [4,4,7,6,7]}nums [4,4,7,6,7]输出[7,7,6] \texttt{[7,7,6]}[7,7,6]解释子序列[7,7] \texttt{[7,7]}[7,7]的和为14 \texttt{14}14不严格大于剩下的其他元素之和14 4 4 6 \texttt{14} \texttt{4} \texttt{4} \texttt{6}14446。因此[7,6,7] \texttt{[7,6,7]}[7,6,7]是满足题意的最小子序列。注意元素按非递增顺序返回。数据范围1 ≤ nums.length ≤ 500 \texttt{1} \le \texttt{nums.length} \le \texttt{500}1≤nums.length≤5001 ≤ nums[i] ≤ 100 \texttt{1} \le \texttt{nums[i]} \le \texttt{100}1≤nums[i]≤100解法思路和算法用sum \textit{sum}sum表示数组nums \textit{nums}nums中的元素之和用subSum \textit{subSum}subSum表示所选的子序列的元素之和则应满足subSum sum − subSum \textit{subSum} \textit{sum} - \textit{subSum}subSumsum−subSum即subSum × 2 sum \textit{subSum} \times 2 \textit{sum}subSum×2sum且所选的子序列的元素个数最少。根据贪心思想在子序列的元素之和下界确定的情况下为了使子序列的元素个数最少应从数组nums \textit{nums}nums按照从大到小的顺序依次选取元素加入子序列直到选取的元素之和subSum \textit{subSum}subSum满足subSum × 2 sum \textit{subSum} \times 2 \textit{sum}subSum×2sum时即得到答案子序列。贪心思想的正确性说明如下。假设按照从大到小的顺序选取元素时至少选取x xx个元素可以满足subSum × 2 sum \textit{subSum} \times 2 \textit{sum}subSum×2sum。如果将最大的x xx个元素中的任意一个元素换成更小的元素则subSum \textit{subSum}subSum将减小此时subSum × 2 sum \textit{subSum} \times 2 \textit{sum}subSum×2sum可能仍成立也可能不成立如果不成立则需要将更多元素加入子序列才能满足subSum × 2 sum \textit{subSum} \times 2 \textit{sum}subSum×2sum此时子序列的元素个数大于x xx。因此按照从大到小的顺序选取元素可以得到元素个数最少的子序列。由于题目要求返回元素个数最少且元素和最大的子序列因此按照从大到小的顺序选取元素加入子序列可以确保当子序列的元素个数最少时元素和最大且子序列的元素顺序为非递增顺序。具体做法是将数组nums \textit{nums}nums按升序排序然后反向遍历数组nums \textit{nums}nums选取元素加入子序列直到子序列的元素之和subSum \textit{subSum}subSum满足subSum × 2 sum \textit{subSum} \times 2 \textit{sum}subSum×2sum时返回子序列。代码classSolution{publicListIntegerminSubsequence(int[]nums){Arrays.sort(nums);intsum0;for(intnum:nums){sumnum;}ListIntegersubsequencenewArrayListInteger();intsubSum0;for(intinums.length-1;i0subSum*2sum;i--){intnumnums[i];subSumnum;subsequence.add(num);}returnsubsequence;}}复杂度分析时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)其中n nn是数组nums \textit{nums}nums的长度。排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间排序之后反向遍历数组需要O ( n ) O(n)O(n)的时间因此时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。空间复杂度O ( log ⁡ n ) O(\log n)O(logn)其中n nn是数组nums \textit{nums}nums的长度。排序需要O ( log ⁡ n ) O(\log n)O(logn)的递归调用栈空间。注意返回值不计入空间复杂度。