【刷题日记】744. 寻找比目标字母大的最小字母

本次刷题日记的第 23 篇，力扣题为：744. 寻找比目标字母大的最小字母 ，简单

一、题目描述：

清明小长假第一天，leetcode 给我们准备了一个简单题，我们一起来看看，查看一下记录，之前写 C/C++ 的时候原来也刷过这道题，本次可以使用 golang 再来回顾一下

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

说是回顾这道题，实际上也是重新做这道题，xdm 自己刷题的情况是不是也是这样呢？

不过没有关系，只要我们曾经思考过并实际解决过，哪怕再次遇到类似的问题，我们肯定是可以很快的找到感觉，找到正确的解决方式

一起来看看本题给出的重点信息吧：

• letters 数组给出的是一个从小到大有序的 byte 数组，且其中字符全部都是小写字母
• letters 数组的长度是 2 -- 104 ，最小都会有 2 个元素
• 题目给出 target 字符也是小写的，要求在 letters 数组中找到比 target 字符大的最小字符

根据上述情况，我们需要明白的，找出比 target 字符大的最小字符的含义

例如 letters 数组中是 [a,f,g] ，如果 target 是 b ，此时 我们识别到 f 和 g 都是大于 b 的，但是 f 才是满足要求的

我们分析一下这个题，实际就是有 2 种 情况

第一种

就是按照题意，当 target 给出的字符是大于或者等于 letters 的最后一个字符的时候，那么得到的结果是 letters[0] 才是满足要求的 ， 因为题目中有说到，这个数组是依次循环出现的

第二种

剩余的情况就是不考虑依次循环的情况，默认是在当前给出的 letters 数组中去找符合要求的字符

当然，这个时候，我们是可以使用遍历 letters 数组的方式去一个一个对比的，但是这个方式也太挫了，我们来使用二分法吧

二分法一般是用在一个有序的数组中查找期望元素的场景，本次的问题正好是符合这个场景，所以理应我们往这个方向去思考

举一个例子：

示例： letters = ["c","f","j","k","m","o","q"], target = "n"

使用二分法进行处理，第一次：

left = 0，right = len(letters) = 6, mid = 3，此时 letters[3] == “k” < "n" ，则进行第二轮

left = 4 , right = 6 , mid = 5 , 此时 letters[5] == "o" > "n" ，则进行第三轮

left = 4, right = 5, 此时 letters[4] == "m" < "n" ，则进行第四轮

left = 5, right = 5 , 校验到 left 已经满足 大于或者等于 right ，则最终的需要找的目标字符就是 letters[5] == “o”

按照上述逻辑和思路，相信编码的话就不是什么难事了吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码 ， 这里需要注意当 target 大于等于 letters[len(letters) -1] 的情况，此处直接返回结果即可

编码如下：

func nextGreatestLetter(letters []byte, target byte) byte {
    // 因为 letters 是有序的，如果 target 大于 letters 数组的最后一位，那么 letters[0] 就是符合要求的字符
    if target >= letters[len(letters)-1] {
        return letters[0]
    }
    // 初始化左边界，右边界 ，和 mid 
    left := 0
    right := len(letters)
    mid := 0
    for left<right {
        mid = (left + right) /2
        // 如果 target 小于 letters 目前边界的中间位置的数字，说明符合要求的字母是在偏左的一侧
        if letters[mid] > target {
            right = mid
        }else{
            // 反之亦然
            left = left + 1
        }
    }
    // 当然 left边界等于 right 或者大于 right 的那一刻，letters[left] 就是我们需要找的比目标大的最小字母
    return letters[left]
}

根据上述编码的话，应该就很清晰了，需要分清咱们需要查找的字符应该是在左边还是右边

四、总结：

本次题目的时间复杂度是 O(logn) ,空间复杂度是 O(1)，因为我们引入了常熟级别的空间消耗

原题地址：744. 寻找比目标字母大的最小字母

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

欢迎点赞，关注，收藏

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

好了，本次就到这里

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

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