Minimum Subsequence in Non Increasing Order

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

分析

元素大的更容易让子序列之和更快超过剩余元素之和，将数组降序排序
贪心策略：从大到小依次取元素，直到当前子序列的和严格超过剩余元素的和
由于优先取大的元素，自然能保证子序列长度最小、元素和最大，且结果是非递增排序的

时间复杂度

时间复杂度 O(nlogn)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    vector<int> minSubsequence(vector<int>& nums)
    {
        std::vector<int> res;
        std::sort(nums.begin(), nums.end(), std::greater()); // 1. 降序排序

        int sum = 0;
        for (int x : nums)
            sum += x; // 2. 计算总和

        int cur = 0;
        for (int x : nums)
        {
            cur += x;             // 当前子序列的和
            res.push_back(x);      // 加入子序列
            if (cur + cur > sum)   // 当前子序列和 > 剩余元素和
                break;
        }
        return res;
    }
};