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

给你一个字符数组 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]。

解题思路

输入： 一个递增的有序字符数组 letters，一个目标值 target

输出： 返回数组中第一个大于 target 的字符，如果不存在就返回第一个字符

本题属于基础查找类问题，适用于使用二分查找在有序数组中快速定位目标值。

我们通过二分查找不断缩小查找区间，具体步骤如下：

初始化左右边界：left = 0, right = len(nums) - 1

循环执行以下逻辑，直到 left > right：

计算中间位置 mid = (left + right) // 2

• 若 nums[mid] <= target，说明大于目标的字符在右半部分，更新 left = mid + 1
• 若 nums[mid] > target，说明 [left, mid] 区间还可能存在大于 target 的字符，更新 right = mid - 1

最后循环结束 left 所在的位置一定是 大于目标的第一个数

但也可能超出数组（最后一个数也可能小于等于 target），所以还需要 left % len(letters) 或者直接取第一个值。

代码实现

python

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        left, right = 0, len(letters) - 1  # 初始化左右指针

        # 二分查找，寻找第一个比 target 大的字符
        while left <= right:
            mid = (left + right) // 2  # 计算中间位置
            if letters[mid] <= target:
                # 如果中间字符小于等于目标字符，说明答案在右边
                left = mid + 1
            else:
                # 如果中间字符大于目标字符，说明答案可能在左边（包括当前mid）
                right = mid - 1

        # 此时 left 是第一个大于 target 的字符的下标
        # 如果 left 超出了数组范围，说明 target 大于等于所有字符
        # 因为题目说是“环形”的，所以返回 letters[0]
        return letters[left % len(letters)]

javascript

/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function(letters, target) {
    let left = 0;
    let right = letters.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (letters[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return letters[left % letters.length];
};

复杂度分析

时间复杂度：O(log n)

空间复杂度：O(1)

链接

744 国际版

744 中文版