0744. 寻找比目标字母大的最小字母 #

标签：数组、二分查找
难度：简单

题目大意 #

给定一个排序后的字符列表 letters，列表中只包含小写英文字母。再给定一个目标字符 target。从列表中找出比 target 更大的最小字母。

假设字母是依次循环的，比如：…、x、y、z、a、b、…

解题思路 #

利用二分查找，找到比 target 大的字母。注意 target 可能大于 letters 的所有字符，此时应返回 letters 的第一个字母。

我们可以假定 target 的取值范围为 [0, len(letters)]。当 target 取到 len(letters) 时，说明 target 大于 letters 的所有字符，对 len(letters) 取余即可得到 letters[0]。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        n = len(letters)
        left = 0
        right = n
        while left < right:
            mid = left + (right - left) // 2
            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return letters[left % n]