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

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

🎯 问题描述（来源于LeetCode）

描述：
给你一个排序后的字符列表 letters，列表中只包含小写英文字母。
另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。

• 如果目标字母 target 大于或等于列表中的最后一个字母，则返回列表中的第一个字母。

说明：

• 这是一个二分查找问题。

• 核心逻辑是寻找上界（第一个大于目标值的位置）。

• 需要处理循环数组的特性（即如果找不到比目标大的字母，则返回第一个字母）。

• 示例：

• 示例 1：

输入: letters = ["c", "f", "j"], target = "a"
输出: "c"
解释: 比 'a' 大的最小字母是 'c'。

• 示例 2：

输入: letters = ["c", "f", "j"], target = "c"
输出: "f"
解释: 比 'c' 大的最小字母是 'f'（注意是严格大于）。

• 示例 3：

输入: letters = ["c", "f", "j"], target = "d"
输出: "f"

• 示例 4：

输入: letters = ["c", "f", "j"], target = "k"
输出: "c"
解释: 'k' 比所有字母都大，根据循环规则，返回第一个字母 'c'。

💻 解题思路

思路1：二分查找（上界）

思路1：代码实现

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        # 使用开区间二分查找模板
        left = -1 
        right = len(letters)
        
        # 寻找第一个大于 target 的字母
        while left + 1 < right:
            mid = left + (right - left) // 2
            # 如果中间字母小于等于 target，说明答案在右半部分
            if ord(letters[mid]) <= ord(target):
                left = mid 
            else:
                # 如果中间字母大于 target，说明答案在左半部分（包含 mid）
                right = mid 
        
        # 循环结束后，right 指向第一个大于 target 的位置
        # 如果 right 超出数组范围，说明 target 大于等于所有字母
        # 根据循环规则，返回第一个字母
        if right == len(letters):
            return letters[0]
        
        return letters[right]

思路1：📊 性能分析

• 时间复杂度：$O(\log N)$
  • 其中 $N$ 是数组 letters 的长度。
  • 使用二分查找，每次将搜索范围减半，时间复杂度为 $O(\log N)$。
• 空间复杂度：$O(1)$
  • 只使用了常数个额外变量，没有使用额外的数据结构。

思考

1. 二分查找模板：

   • 代码使用了开区间的二分查找模板：left = -1, right = len(letters)，循环条件为 while left + 1 < right。
   • 这种模板的优点是边界处理简单，不需要考虑 left == right 的情况。
   • 最终返回的 right 就是第一个大于 target 的位置。

2. 比较逻辑：

   • if ord(letters[mid]) <= ord(target):：如果中间字母小于等于 target，说明答案在右半部分（left = mid）。
   • else:：如果中间字母大于 target，说明答案在左半部分（包含 mid），所以 right = mid。
   • 注意这里是严格大于，所以使用 <= 而不是 <。

3. 循环数组处理：

   • 二分查找结束后，right 指向第一个大于 target 的位置。
   • 如果 right == len(letters)，说明 target 大于等于所有字母，根据循环规则，返回第一个字母 letters[0]。
   • 否则，返回 letters[right]。

4. 边界情况：

   • target 小于所有字母：right 为 0，返回 letters[0]。
   • target 等于某个字母：right 指向下一个更大的字母。
   • target 大于所有字母：right 为 len(letters)，返回 letters[0]。