LeetCode 744. 寻找比目标字母大的最小字母

🌈🌈😄😄

欢迎来到茶色岛独家岛屿，本期将为大家揭晓LeetCode 744. 寻找比目标字母大的最小字母 ，做好准备了么，那么开始吧。

🌲🌲🐴🐴

一、题目名称

LeetCode 744. 寻找比目标字母大的最小字母

二、题目要求

三、相应举例

四、限制要求

2 <= letters.length <= 104

letters[i] 是一个小写字母

letters 按非递减顺序排序

letters 最少包含两个不同的字母

target 是一个小写字母

五、解决办法

二分查找

注意点：

六、代码实现

---

一、题目名称

LeetCode 744. 寻找比目标字母大的最小字母

二、题目要求

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'

三、相应举例

示例 1：

输入: letters = ["c", "f", "j"]，target = "a"
输出: "c"

示例 2:

输入: letters = ["c","f","j"], target = "c"
输出: "f"

示例 3:

输入: letters = ["c","f","j"], target = "d"
输出: "f"

四、限制要求

• 2 <= letters.length <= 104

• letters[i] 是一个小写字母

• letters 按非递减顺序排序

• letters 最少包含两个不同的字母

• target 是一个小写字母

五、解决办法

二分查找

注意点：

当char[] letters中没有比target大的字母时，返回首字母。这个题目没有给出，但一提交就会发现。出循环条件为left=right，故返回left即为比目标字母大的最小字母。其余代码可看我其他二分查找文章，这里就不具体阐述了。

六、代码实现

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int length = letters.length;
        if (target >= letters[length - 1]) {
            return letters[0];
        }
        int low = 0, high = length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (letters[mid] > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return letters[low];
    }
}