LeetCode Question of the Day - 1403. Minimum Subsequence in Non-Increasing Order

1.题目描述

1403. 非递增顺序的最小子序列

给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和.

如果存在多个解决方案,只需返回 长度最小 的子序列.如果仍然有多个解决方案,则返回 元素之和最大 的子序列.

与子数组不同的地方在于,「数组的子序列」不强调元素在原数组中的连续性,也就是说,它可以通过从数组中分离一些（也可能不分离）元素得到.

注意,题目数据保证满足所有约束条件的解决方案是 唯一 的.同时,返回的答案应当按 非递增顺序 排列.

示例 1：

输入：nums = [4,3,10,9,8]
输出：[10,9] 
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列.但是 [10,9] 的元素之和最大. 

示例 2：

输入：nums = [4,4,7,6,7]
输出：[7,7,6] 
解释：子序列 [7,7] 的和为 14 ,不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）.因此,[7,6,7] 是满足题意的最小子序列.注意,元素按非递增顺序返回.  

示例 3：

输入：nums = [6]
输出：[6]

2.解题思路与代码

2.1 解题思路

这道题非常简单,The question asks to find the subsequence with the smallest length,And the sum of the subsequences is required to be greater than the sum of the elements outside the subsequence,Then we can think of if the sum of the subsequences is greater than half of the sum of the whole array,Then the sum of this subsequence must be greater than the sum of the rest of the elements.Start with this idea,我们先对数组进行排序,Then start traversing from the position with the largest number.The condition that the subsequence length required by the title is minimum and decreasing,Then we start summing from high,Exit until the sum is greater than half the sum of the array for the first time,This will give you the results.
以 [4,3,10,9,8] 为例,First we sort the array,And find the sum of the array as 34,Then we just need to find greater than 17 的子序列即可

The title requires subsequences in descending order and minimum length,Since the sorting is sorted from small to large,Then we traverse forward from the last bit of the array.when pointing to the last digit,The sum of the subsequences at this time is 10 小于 17.Because the title requires the result list to be sorted in descending order,因此将 10 放入结果列表中,然后继续向前移动

after moving forward,The sum of the subsequences is 19 大于 17 满足条件,将 9 Exit the loop after putting in the result list,At this point the subsequence in the resulting list is [10, 9]

2.2 代码

class Solution {
    
    public List<Integer> minSubsequence(int[] nums) {
    
        int sum = Arrays.stream(nums).sum() >> 1;
        Arrays.sort(nums);
        List<Integer> ans = new ArrayList<>();
        int i = nums.length - 1;
        int tmp = 0;
        while (i >= 0) {
    
            tmp += nums[i];
            ans.add(nums[i]);
            if (tmp > sum) {
    
                break;
            }
            i--;
        }
        return ans;
    }
}ji

2.3 测试结果

通过测试

3.总结

• 对数组进行排序,Then start traversing from the high position
• Find a sequence that is greater than the array value and half