题目描述
思路解析动画文字版
记住「找第一个大于 target 的位置：不大于就 left=mid+1；大于就把 mid 记成候选、right=mid 往左继续找」，下面每帧都在套它。
开始二分:区间用左闭右开 [0, 8) 表示。一旦遇到比 'a' 大的字母,就把它记成「当前可行候选」标绿、再继续往它左边找更小的;灰格是已彻底排除、不再搜的范围。
当前搜索区间 [0, 8) 的正中间是 letters[4]='p'。它严格大于 'a',它会成为新的、更靠左的可行候选。
letters[4]='p' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 4);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
当前搜索区间 [0, 4) 的正中间是 letters[2]='j'。它严格大于 'a',它会成为新的、更靠左的可行候选。绿色那格是目前记下的可行候选。
letters[2]='j' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 2);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
当前搜索区间 [0, 2) 的正中间是 letters[1]='f'。它严格大于 'a',它会成为新的、更靠左的可行候选。绿色那格是目前记下的可行候选。
letters[1]='f' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 1);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
当前搜索区间 [0, 1) 的正中间是 letters[0]='c'。它严格大于 'a',它会成为新的、更靠左的可行候选。绿色那格是目前记下的可行候选。
letters[0]='c' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 0);只把它右边灰掉。此时区间 [0, 0) 收空,保留的候选下标 0('c')就是答案。
二分结束,left 停在 0,letters[0]='c' 就是第一个严格大于 'a' 的字母(绿色),即答案。
开始二分:区间用左闭右开 [0, 8) 表示。一旦遇到比 'm' 大的字母,就把它记成「当前可行候选」标绿、再继续往它左边找更小的;灰格是已彻底排除、不再搜的范围。
当前搜索区间 [0, 8) 的正中间是 letters[4]='p'。它严格大于 'm',它会成为新的、更靠左的可行候选。
letters[4]='p' 比 'm' 大,把它记成新的、更靠左的可行候选(绿色移到下标 4);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
当前搜索区间 [0, 4) 的正中间是 letters[2]='j'。它不大于(≤) 'm',它和它左边都不可能是答案,答案在它右边。绿色那格是目前记下的可行候选。
letters[2] 不大于 'm',把 mid 及它左边整段灰掉排除,left 收到 3。绿色候选不动,继续在它左边找更小的。
当前搜索区间 [3, 4) 的正中间是 letters[3]='m'。它不大于(≤) 'm',它和它左边都不可能是答案,答案在它右边。绿色那格是目前记下的可行候选。
letters[3] 不大于 'm',把 mid 及它左边整段灰掉排除,left 收到 4。区间 [4, 4) 收空,保留的候选下标 4('p')就是答案。
二分结束,left 停在 4,letters[4]='p' 就是第一个严格大于 'm' 的字母(绿色),即答案。
开始二分:区间用左闭右开 [0, 8) 表示。一旦遇到比 'z' 大的字母,就把它记成「当前可行候选」标绿、再继续往它左边找更小的;灰格是已彻底排除、不再搜的范围。
当前搜索区间 [0, 8) 的正中间是 letters[4]='p'。它不大于(≤) 'z',它和它左边都不可能是答案,答案在它右边。
letters[4] 不大于 'z',把 mid 及它左边整段灰掉排除,left 收到 5。区间每次砍一半。
当前搜索区间 [5, 8) 的正中间是 letters[6]='t'。它不大于(≤) 'z',它和它左边都不可能是答案,答案在它右边。
letters[6] 不大于 'z',把 mid 及它左边整段灰掉排除,left 收到 7。区间每次砍一半。
当前搜索区间 [7, 8) 的正中间是 letters[7]='x'。它不大于(≤) 'z',它和它左边都不可能是答案,答案在它右边。
letters[7] 不大于 'z',把 mid 及它左边整段灰掉排除,left 收到 8。区间收空且没有候选,说明没有比 'z' 大的,稍后环形回 letters[0]。
二分结束 left=8 等于数组长度——说明没有字母比 'z' 大,按环形规则回到开头,答案是 letters[0]='c'(绿色)。
边界先想清：相等要跳过；无更大者(target≥末位)靠环形回 letters[0]；单元素无需特判，它比 target 大就直接返回、否则才环形。
认出「找第一个满足条件的位置」这个母题，二分就不再靠背模板。
参考代码
from typing import Listclass 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)]复杂度
- 时间：O(log n)，每次范围减半
- 空间：O(1)，只用 left、right 两个下标
易错点
面试追问把动画讲成自己的话
追问这其实是哪一类二分？
追问为什么用左闭右开而不是双闭区间？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
搜索旋转排序数组
LeetCode 33 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题