744.寻找比目标字母大的最小字母

目标

给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

示例 1：

输入: letters = ['c', 'f', 'j']，target = 'a'
输出: 'c'
解释：letters 中字典上比 'a' 大的最小字符是 'c'。

示例 2:

输入: letters = ['c','f','j'], target = 'c'
输出: 'f'
解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。

示例 3:

输入: letters = ['x','x','y','y'], target = 'z'
输出: 'x'
解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。

说明：

• 2 <= letters.length <= 10^4
• letters[i] 是一个小写字母
• letters 按非递减顺序排序
• letters 最少包含两个不同的字母
• target 是一个小写字母

思路

有一个升序排列的字符数组 letters，返回大于 target 的最小字符，如不存在返回第一个字符。

使用二分，查找第一个大于 target 的字符。

代码

/**
 * @date 2026-02-02 9:42
 */
public class NextGreatestLetter744 {

    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        int r = n - 1;
        int l = 0;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (letters[m] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return l < n ? letters[l] : letters[0];
    }

}

性能