【刷题日记】1403. 非递增顺序的最小子序列

一、题目描述：

继续开始我们的每日一题，做一做非递增顺序的最小子序列

二、这道题考察了什么思想？你的思路是什么？

看到子序列，我们是否会想到之前我们做过的很多关于子序列的题目呢，这一次的子序列又有啥不一样的呢，来仔细看看题目

看看题目，我们知道有如下几个要求：

• 题目给出一个乱序的序列，要求我们输出非递增的子序列
• 对于输出的子序列题目有两个要求

• 序列长度最短，要求序列和大于剩余序列和，且出现同种情况取数值较大的一种

分析

如何去思考这道题目呢，题目要求我们输出非递增的序列，意味着，我们需要做排序操作这个是没得说的

还要求我们输出的序列和要大于剩余的序列和，意味着，我们需要做数据的求和与比较

其实看到这里就比较明确了，稍加梳理，我们就知道如何去落地这么一个小需求了

例如，示例中，我们可以看到

接下来咱们就来撸代码吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，咱们需要做这些事情

• 排序，从大到小排序
• 求和
• 贪心，从最大的数字开始累加，第一次累加和大于剩下的数字和为止

编码如下：

func minSubsequence(nums []int) []int {
    // 排序，从大到小排序
    sort.Sort(sort.Reverse(sort.IntSlice(nums)))
    // 求和
    var total int
    for _,num := range nums {
        total += num
    }
    // 贪心，从最大的数字开始累加，第一次累加和大于剩下的数字和为止
    var sum int
    for i,num := range nums {
       sum += num
       if sum > total - sum {
           return nums[:i+1] 
       }
    }
    return []int{}
}

四、总结：

时间复杂度是多少呢，我们知道咱们使用了库里面的排序算法，一般是使用了快速排序，因此咱们的的时间复杂度是 O(nlogn)

空间复杂度是 O(1) 吗？ nonono， 虽然显示的我们没有占用其他的空间消耗，实际上比较大的空间消耗是是 O(logn) ，也是消耗在排序上面的

原题地址：1403. 非递增顺序的最小子序列

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~