| 题目链接 | 744. 寻找比目标字母大的最小字母 |
|---|---|
| 思路 | 二分法 |
| 题解链接 | 官方题解 |
| 关键点 | 循环不变量（开区间）：letters[left] < target && letters[right] >= target |
| 时间复杂度 | \(O(\log n)\) |
| 空间复杂度 | \(O(1)\) |
代码实现：
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
if target < letters[-1]:
left, right = -1, len(letters)
target = chr(ord(target) + 1)
while left + 1 < right:
mid = (left+right) // 2
if letters[mid] < target:
left = mid
else:
right = mid
return letters[right]
return letters[0]
Python-库函数
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
if target < letters[-1]:
return letters[bisect_right(letters, target)]
return letters[0]