LeetCode 744简单二分查找
寻找比目标字母大的最小字母 图解题解
这道题到底在问什么
升序字母数组 letters 与目标 target：返回严格大于 target 的最小字母；不存在则返回 letters[0]。要求 O(log n)。
- 输入
- letters=['c','f','j'], target='a'
- 输出
- 'c'
- 输入
- letters=['c','f','j'], target='j'
- 输出
- 'c' （无更大者，环形回首）
最优解：一步一步想明白
- 3记住「找第一个大于 target 的位置：不大于就 left=mid+1；大于就把 mid 记成候选、right=mid 往左继续找」，下面每帧都在套它。
- 4开始二分:区间用左闭右开 [0, 8) 表示。一旦遇到比 'a' 大的字母,就把它记成「当前可行候选」标绿、再继续往它左边找更小的;灰格是已彻底排除、不再搜的范围。
- 5当前搜索区间 [0, 8) 的正中间是 letters[4]='p'。它严格大于 'a',它会成为新的、更靠左的可行候选。
- 6letters[4]='p' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 4);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
- 7当前搜索区间 [0, 4) 的正中间是 letters[2]='j'。它严格大于 'a',它会成为新的、更靠左的可行候选。绿色那格是目前记下的可行候选。
- 8letters[2]='j' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 2);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
- 9当前搜索区间 [0, 2) 的正中间是 letters[1]='f'。它严格大于 'a',它会成为新的、更靠左的可行候选。绿色那格是目前记下的可行候选。
- 10letters[1]='f' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 1);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
- 11当前搜索区间 [0, 1) 的正中间是 letters[0]='c'。它严格大于 'a',它会成为新的、更靠左的可行候选。绿色那格是目前记下的可行候选。
- 12letters[0]='c' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 0);只把它右边灰掉。此时区间 [0, 0) 收空,保留的候选下标 0('c')就是答案。
- 13二分结束,left 停在 0,letters[0]='c' 就是第一个严格大于 'a' 的字母(绿色),即答案。
- 14开始二分:区间用左闭右开 [0, 8) 表示。一旦遇到比 'm' 大的字母,就把它记成「当前可行候选」标绿、再继续往它左边找更小的;灰格是已彻底排除、不再搜的范围。
- 15当前搜索区间 [0, 8) 的正中间是 letters[4]='p'。它严格大于 'm',它会成为新的、更靠左的可行候选。
- 16letters[4]='p' 比 'm' 大,把它记成新的、更靠左的可行候选(绿色移到下标 4);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
- 17当前搜索区间 [0, 4) 的正中间是 letters[2]='j'。它不大于(≤) 'm',它和它左边都不可能是答案,答案在它右边。绿色那格是目前记下的可行候选。
- 18letters[2] 不大于 'm',把 mid 及它左边整段灰掉排除,left 收到 3。绿色候选不动,继续在它左边找更小的。
- 19当前搜索区间 [3, 4) 的正中间是 letters[3]='m'。它不大于(≤) 'm',它和它左边都不可能是答案,答案在它右边。绿色那格是目前记下的可行候选。
- 20letters[3] 不大于 'm',把 mid 及它左边整段灰掉排除,left 收到 4。区间 [4, 4) 收空,保留的候选下标 4('p')就是答案。
- 21二分结束,left 停在 4,letters[4]='p' 就是第一个严格大于 'm' 的字母(绿色),即答案。
- 22开始二分:区间用左闭右开 [0, 8) 表示。一旦遇到比 'z' 大的字母,就把它记成「当前可行候选」标绿、再继续往它左边找更小的;灰格是已彻底排除、不再搜的范围。
- 23当前搜索区间 [0, 8) 的正中间是 letters[4]='p'。它不大于(≤) 'z',它和它左边都不可能是答案,答案在它右边。
- 24letters[4] 不大于 'z',把 mid 及它左边整段灰掉排除,left 收到 5。区间每次砍一半。
- 25当前搜索区间 [5, 8) 的正中间是 letters[6]='t'。它不大于(≤) 'z',它和它左边都不可能是答案,答案在它右边。
- 26letters[6] 不大于 'z',把 mid 及它左边整段灰掉排除,left 收到 7。区间每次砍一半。
- 27当前搜索区间 [7, 8) 的正中间是 letters[7]='x'。它不大于(≤) 'z',它和它左边都不可能是答案,答案在它右边。
- 28letters[7] 不大于 'z',把 mid 及它左边整段灰掉排除,left 收到 8。区间收空且没有候选,说明没有比 'z' 大的,稍后环形回 letters[0]。
- 29二分结束 left=8 等于数组长度——说明没有字母比 'z' 大,按环形规则回到开头,答案是 letters[0]='c'(绿色)。
⚠️ 容易写错的地方
✗ 错：用 ≤ 还是 < 搞混
✓ 对：要严格大于，所以 letters[mid] ≤ target 时排除
题目要求严格大于，相等的也得跳过
✗ 错：结束后忘了取模
✓ 对：return letters[left % n] 处理环形
left 可能等于 n（无更大者），取模回到 0
✗ 错：区间开闭不一致导致死循环
✓ 对：统一左闭右开 [left, right)
收缩规则 left=mid+1 / right=mid 与开闭必须配套
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
left, right = 0, len(letters)
while left < right:
mid = (left + right) // 2
if letters[mid] <= target:
left = mid + 1
else:
right = mid
return letters[left % len(letters)]C++
#include <vector>
using namespace std;
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int left = 0, right = letters.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (letters[mid] <= target) left = mid + 1;
else right = mid;
}
return letters[left % letters.size()];
}
};Java
import java.util.*;
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int left = 0, 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];
}
}复杂度
时间
O(log n)
每次范围减半
空间
O(1)
只用 left、right 两个下标
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 寻找比目标字母大的最小字母 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这其实是哪一类二分？+
是「二分查找第一个满足条件的位置」（lower_bound 思想）。条件为 letters[mid] > target，找最左的 True。把题目翻译成「第一个 True 在哪」，一大批二分题都能套这个左闭右开模板。
为什么用左闭右开而不是双闭区间？+
左闭右开 [left, right) 的收缩规则 left=mid+1 / right=mid 不会漏元素也不会死循环，且结束时 left 恰好是答案位置，配合 % n 处理环形非常自然。双闭也能写，但边界更易错。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 寻找比目标字母大的最小字母 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。