LeetCode 744. 寻找比目标字母大的最小字母 - 遍历解法

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

1. 整体思路

核心问题

在一个有序（通常是非递减顺序）的字符数组 letters 中，找到比目标字符 target 大的最小字符。

• 如果不存在比 target 大的字符，则返回数组的第一个字符（循环比较）。

算法逻辑

1. 特性利用：数组 letters 已经是排序过的。
2. 顺序遍历：
   • 从左到右遍历数组。
   • 由于数组是有序的，我们遇到的第一个比 target 大的字符 c，一定就是所有比 target 大的字符中最小的那个。
   • 一旦找到，直接返回该字符。
3. 循环兜底：
   • 如果遍历完整个数组都没有找到比 target 大的字符（说明 target 大于或等于数组中的所有字符），根据题目要求（'letters wrap around'），应该返回数组的第一个字符 letters[0]。

---

2. 完整代码

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        // 遍历排序后的字符数组
        for (char c : letters) {
            // 核心判断：因为数组是有序的，第一个满足 c > target 的字符
            // 必然是比 target 大的最小字符。
            if (target < c) {
                return c;
            }
        }
        // 如果循环结束仍未返回，说明数组中没有比 target 大的字符
        // 根据题目"循环"的要求，返回数组第一个元素
        return letters[0];
    }
}

---

3. 时空复杂度

假设数组 letters 的长度为 N。

时间复杂度：O(N)