【刷题日记】899. 有序队列

本次刷题日记的第 86 篇，力扣题为：899. 有序队列

一、题目描述：

有序队列，这是一个字符串的题目，看看需要如何处理

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

题目中给出的描述，实际上是需要我们按照条件，将原有字符串，调整成一个字典上最小的字符串，简单来说，尽可能的按照从小到大排序这个字符串

分析

咱们根据题目可以知道，需要关注题目给出的 k 的值，我们注意看 当 k == 1的时候，我们无论如何，都只能将字符串的第1个字符移动到尾部，来比较是不是字典序最小的

例如示例 1 中, k==1

源串	c	b	a
调整 1 次	b	a	c
调整 2 次	a	c	b

调整后，我们进行比较，发现 acb 才是最小的

若 还是 示例 1 ，但是我们令 k == 2 ，看看会有啥不一样的

源串	c	b	a
调整 1 次	b	a	b
调整 2 次	a	b	c

调整后，我们发现答案是 abc，当然，不要关注调整的次数，这个次数是根据实际的字符串而变动的

实际上我也不用举太多的例子了，细心的我们可以发现

当 k = 2 的时候，我们总是能在字符串的前 k（k>1） 个字符中选择最小的一个字符丢到字符串尾部，直到整个字典序是最小的

经过我们多次试验之后，可以发现，实际上就是对字符串进行排序而已

那么，接下来就是翻译代码的时候了，根据这个分析来看，其实这个题蛮简单的，只需要考虑清楚 k 为 1 和 大于 1 的情况

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

• 需要明确分类处理 k == 1的情况，咱们只能 1 个字符 1 个字符的向字符串尾巴后面移动，来比较大小

• K > 1 的时候，按照上述分析，咱们直接排序就可以了

编码如下：

func orderlyQueue(s string, k int) string {
    if k == 1 {
        res := s
        for i := 1; i < len(s); i++ {
            // 将第一个元素移动到最后，查看哪个字符串最大
            s = s[1:] + s[:1]
            if s < res {
                res = s
            }
        }
        return res
    }
    t := []byte(s)
    sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
    return string(t)
}

四、总结：

这个题咱们的解决方式其实还是比较明确和简单的，可能看上去时间复杂度可能会有点高，此处的时间复杂度我们需要从 2 个方面来看，k为 1的情况，咱们的时间复杂度是 O(n^2)，空间复杂度是 O(n)

当 k>1 的情况下，我们可以看出来，咱们使用了排序算法，时间复杂度是 O(nlogn)

原题地址：899. 有序队列

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

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

好了，本次就到这里

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

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