LeetCode 744. 寻找比目标字母大的最小字母
题目描述
题意分析
字母数组按非递减顺序排列，可以有重复值。返回其中严格大于
target的最小字母；如果所有字母都不大于它，就返回数组的第一个字母。
解法：二分寻找严格上界
核心思路
[!blue]
数组有序，所以“不大于
target”的字母在前，“大于target”的字母在后。两部分之间的第一个位置就是严格上界，而该位置上的字母也一定是符合要求的最小字母。用
[left, right)保存尚未判断的下标，初始为[0, n)。始终保持：left之前的字母都不大于目标，right及其之后的字母都大于目标。若letters[mid] <= target，中点及其左侧都不能作为答案，令left = mid + 1；否则中点及其右侧都满足条件，但左边可能还有更早的答案，令right = mid。每次更新都会缩小待判断区间。结束时
left == right，两个已确定区域恰好相接，边界就是第一个大于目标的位置。相等的字母会统一被归入左侧，因此重复值也不会改变这一结论。边界可能是
n，表示右侧没有任何字母，此时按题意回到下标 0。由于最终left只可能落在[0, n]，left % n可以统一完成正常访问与回绕；题目保证数组非空，所以取模安全。
解题步骤
- 初始化
left = 0、right = n。- 在
left < right时取中点；小于或等于目标就排除中点及左侧，否则将右边界收至中点。- 两边界相遇后，返回
letters[left % n]。
代码实现
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int left = 0;
int right = letters.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (letters[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return letters[left % letters.length];
}
}
func nextGreatestLetter(letters []byte, target byte) byte {
left, right := 0, len(letters)
for left < right {
mid := left + (right-left)/2
if letters[mid] <= target {
left = mid + 1
} else {
right = mid
}
}
return letters[left%len(letters)]
}
复杂度分析
- 时间复杂度：$O(\log n)$，每轮将待判断区间大致减半。
- 空间复杂度：$O(1)$，只维护二分边界和中点。
关键点总结
[!green]
- 等于目标的字母也必须排除，寻找的是严格上界。
- 目标小于全部字母时，边界为 0；目标不小于最大字母时，边界为
n，两种情况都返回首字母。- 循环中
mid < right <= n，不会读取虚拟边界letters[n]。
易错点总结
[!yellow]
- 不能在遇到等于 target 时返回，题目要求严格大于。
- 二分结果可以等于 n，访问前必须处理回绕。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 35. 搜索插入位置 | 简单 | 把判定从大于等于改为严格大于，即得到本题的右侧边界。 |
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 查找最后一个等于目标的位置，也可以用严格上界减一完成。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！