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

难度: 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]。

提示：

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

Submission

运行时间: 19 ms

内存: 17.7 MB

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        n = len(letters)
        left = 0
        right = n
        while left < right:
            mid = left + (right - left) // 2
            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return letters[left % n]

Explain

这个题解使用了二分查找的思路。首先定义左右指针 left 和 right，分别指向数组的开始和结束位置。然后进行二分查找，每次取中间位置 mid，判断 letters[mid] 和 target 的大小关系。如果 letters[mid] <= target，表示要找的字符在 mid 的右侧，将 left 更新为 mid + 1；否则表示要找的字符在 mid 的左侧或就是 mid，将 right 更新为 mid。最后，当 left >= right 时，二分查找结束，left 指向的位置就是第一个大于 target 的字符。如果 left 越界，则取 left % n 作为结果下标，即环形数组的处理方式。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        n = len(letters)
        left = 0
        right = n
        while left < right:
            mid = left + (right - left) // 2
            if letters[mid] <= target:
                # 当前字符小于等于目标字符，向右搜索
                left = mid + 1
            else:
                # 当前字符大于目标字符，向左搜索
                right = mid
        # 返回环形数组中第一个大于目标字符的字符
        return letters[left % n]

Explore

在此二分查找变体中，right 初始化为 n 而不是 n-1 是为了确保搜索空间包括数组中可能存在的最后一个元素。这种方法特别适用于寻找'第一个满足某条件的元素'的场景。当最后一个元素可能满足条件时，初始化 right 为 n 使得左闭右开的搜索区间能够覆盖到整个数组。此外，这样做也便于处理环形数组的情况，即当所有元素都不满足条件时可以通过模运算返回数组的第一个元素。

当数组中所有字符都小于或等于 target 时，根据二分查找的逻辑，left 指针会逐步向右移动直至超出数组的右边界，即 left 最终将等于 n。由于需要返回比 target 大的最小字符，且数组是按顺序排列的，所以当 left 等于 n 时，按照环形数组的处理方式，通过执行 left % n，结果将为 0，从而返回数组的第一个字符。

在处理目标字符大于 letters 中所有字符的情况时，采用 left % n 来获取结果下标是为了处理数组的环形特性。在此情况下，left 会增加到 n，表示搜索空间已超出数组的实际范围。使用 left % n 可以将索引环绕到数组的开始，即从数组的头开始寻找符合条件的字符。这种方法总是有效的，因为它确保了即使索引超出了数组长度，也能正确地环绕到数组的有效位置。

如果 letters 数组为空，当前代码没有直接处理这种情况，这可能导致在执行二分查找时出现索引错误（如尝试访问 letters[mid] 时）。因此，在实际应用中确实需要增加对空数组的检查。在调用此方法前，应该先检查数组是否为空，如果为空，则应该返回一个合理的默认值或抛出异常，以避免运行时错误。