寻找比目标字母大的最小字母 图解题解

升序字母表里，挑出比 target 大的最小那个

给一排升序（从小到大排好）的小写字母 letters 和目标 target，返回严格大于 target 的最小字母；一个都不比它大就绕回开头返回 letters[0]。题面 ['c','f','j']：target='a' 答案 'c'；target='j' 环形回 'c'。题目还卡死 O(log n)。

逐个字母往后比，为什么配不上 O(log n)

从头往后逐个和 target 比，遇到第一个更大的就停。n 个字母最坏要比满 n 次，是 O(n)。字母表顶多 26 个不多，可换到几十万长的升序数组就卡死，O(log n) 正是要堵掉逐个比。

字母表排好序，半排可以一次跳过

钥匙在『升序』。挨个位置问『这字母严格大于 target 吗』，答案一定前一串否、后一串是：某字母超过 target 后右边全超过。要找从否到是的分界后第一个是。看中点，不大于 target 连左边一起丢，大于就右半不看、它自己留候选。

普通二分撞到相等就返回，这里相等不算数：'j' 不比 'j' 大得跳过。所以只分两支：≤ target 往右扔、> target 收进候选，即库函数 upper_bound（第一个严格大于目标的位置）。

中点比完，左界右界各挪到哪

用左闭右开区间 [left, right) 框住待查位置。起手 left=0、right=n（n 不是 n-1，给越界回首留落点）。每轮 mid=(left+right)//2 看 letters[mid]：≤ target 就 left=mid+1；> target 时 mid 可能是答案、不能扔，right=mid 往左继续找。收空时 left 停在第一个是。

整排都不比 target 大时 left 涨到 n，返回 letters[left % n]：取模把 n 变回 0、绕回 letters[0]，省掉 if。

['c','f','j'] 找 'a'、找 'j' 各走几轮

先找 'a'。left=0、right=3，mid=1，'f' ≤ 'a' 不成立，right 收到 1。第二轮 mid=0，'c' ≤ 'a' 也不成立，right 收到 0。left=right=0 收空，返回 letters[0 % 3]='c'。

再看 target='j'（触发环形）。mid=1，'f' ≤ 'j' 成立，left 跳到 2。第二轮 mid=2，'j' ≤ 'j' 相等也算 ≤，left 跳到 3。收空，left=3=n，返回 letters[3 % 3]='c'，取模绕回开头。

收完 left 可能正好等于 n，直接读就越界

每比一次区间减半，最多 log₂n 轮，时间 O(log n)；只动 left、right 两个下标，空间 O(1)。

判断丢等号写成 letters[mid] < target，相等的字母混进候选。收缩后 left 可能等于 n，直接 letters[left] 会越界，靠 letters[left % n] 绕回 0。左闭右开配 left=mid+1 / right=mid，抄双闭 right=mid-1 会漏格或死循环。

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];
    }
}