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

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

题目传送门

点击这里

解题思路

一道简单题，用的是贪心思想，我们可以事先记录好总和，然后从后往前遍历，每次比较下遍历过的数的和与总和的差值的大小，然后添加到结果。

代码

func minSubsequence(nums []int) []int {
    // 计算总和
    sum := 0
    for _, v := range nums {
        sum += v
    }
    // 非递增的顺序，且使用贪心的思想
    var res []int
    sort.Ints(nums)
    s := 0
    for i := len(nums)-1;i >= 0;i -- {
        s += nums[i]
        res = append(res, nums[i])
        if s > sum - s {
            return res
        }
    }
    return []int{}
}