当前位置：网站首页>leetcode-每日一题1403. 非递增顺序的最小子序列（贪心）

leetcode-每日一题1403. 非递增顺序的最小子序列（贪心）

2022-08-05 03:19:00 【lin钟一】

在这里插入图片描述
题目链接：https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/

思路

方法一、贪心

题目的大致意思就是把数组分成两个序列，一个序列元素之和严格大于另一个序列元素之和，且满足前面的序列元素最大、长度最短两个要求，所以很简单，我们只需要把数组从大到小排序一遍，计算整个数组之和，然后贪心去取数组的最大值，直到序列元素之和严格大于另一个序列元素之和

代码示例

func minSubsequence(nums []int) []int {
    
    sort.Slice(nums, func(i, j int) bool {
     return nums[i] > nums[j]})
    tot := 0
    for _, num := range nums {
    
        tot += num
    }
    for i, sum := 0, 0; ; i++ {
    
        sum += nums[i]
        if sum > tot-sum {
    
            return nums[:i+1]
        }
    }
}