寻找比目标字母大的最小字母
解题思路：
-
首先比较目标字母和列表中的最后一个字母，当目标字母大于或等于列表中的最后一个字母时，返回首个字母；
-
先找到小于等于 target 的最大字母，返回这个字母的下一个即可（可以看成取所有小于等于 target 区间的右边界）；
复杂度：
-
时间复杂度：O(logn)，其中 n 是列表 letters 的长度；
-
空间复杂度：O(1)；
代码实现：
function nextGreatestLetter(letters: string[], target: string): string {
let len = letters.length;
// target 大于 letters 里面的最大值，直接返回第一项
if (target >= letters[len - 1]) return letters[0];
let left = 0;
let right = len - 1;
// 可以看成求 小于等于 target 区间的右边界
while (left <= right) {
let mid = left + (right - left >> 1);
if (letters[mid] === target) {
left = mid + 1;
} else if (letters[mid] < target) {
left = mid + 1;
} else if (letters[mid] > target) {
right = mid - 1;
}
}
return letters[left];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 69. x 的平方根
上一篇
评论
