744. Find Smallest Letter Greater Than Target

📘 題目敘述

給定一個排序過的字元陣列 letters（只包含小寫英文字母），以及一個字元 target。

請找出 letters 中 嚴格大於 target 的最小字母，並回傳它。

• letters 會被視為「環狀」：
  • 如果不存在比 target 更大的字母，就回傳 letters[0]。

條件限制

• 2 <= letters.length <= 10^4
• letters[i] 是小寫英文字母
• letters 依照遞增排序
• letters 至少包含兩個不同的字母
• target 是小寫英文字母

🧠 解題思路

我的做法是用最直觀的線性掃描：

1. 先處理「環狀」的特例：如果 target 大於等於最後一個字母，那答案一定回到第一個字母
2. 否則就從左到右掃描 letters，第一個滿足 a > target 的字母就是答案（因為陣列已排序）

這樣做的重點是：

• 排序保證「第一個大於 target 的字母」就是最小的那個

所有變數

• letters：排序後的字元陣列
• target：要比較的目標字元

🪜 主要流程步驟

1. 先判斷是否需要環狀回到開頭

• 如果 letters[n - 1] <= target
  • 代表整個陣列裡最大的字母都沒有比 target 大
  • 所以答案一定是 letters[0]

2. 從左到右找第一個大於 target 的字母

• 依序掃描每個字母 a
• 只要遇到 a > target：
  • 直接回傳 a
  • 因為它一定是「最小的可行答案」（排序性質）

3. 保底回傳

• 理論上前面已經處理完所有情況
• 最後 return letters[0] 是保底寫法（避免編譯器警告 / 防呆）

💻 程式碼實作

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int n = letters.size();
        if (letters[n - 1] <= target) {
            return letters[0];
        }
        for (char a : letters) {
            if (a > target) {
                return a;
            }
        }
        return letters[0];
    }
};

🔗 題目連結

https://leetcode.com/problems/find-smallest-letter-greater-than-target/