744. 尋找比目標字母大的最小字母

思路

經典的二分搜尋題目

如果對過程有疑慮，將過程打印出來就好。
推薦開區間寫法，比較簡潔。

程式碼

1. 閉區間二分

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int n = letters.size();
        int left = 0, right = n - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(letters[mid] > target) { // 中間的滿足，更好的答案只會出現在左半邊
                right = mid - 1;
            }
            else { // 中間不滿足，更好的答案只會在右半邊
                left = mid + 1;
            }
        }
        // 跳出迴圈代表此時 left > right, 答案是 right + 1, 也就是 left 
        return right == n - 1 ? letters[0] : letters[left];
    }
};

2. 開區間二分

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int n = letters.size();
        int left = -1, right = n;
        while(left + 1 < right) {
            int mid = left + (right - left) / 2;
            (letters[mid] > target ? right : left) = mid; 
        }
        return letters[right % n]; 
    }
};

3. 庫函數

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        // 找到第一個嚴格大於 target 的字元所在的位置。
        auto it = upper_bound(letters.begin(), letters.end(), target); 
        return it == letters.end() ? letters[0] : *it; // it = letters.end() 代表沒找到
    }
};

複雜度分析

• 時間複雜度：$O(\log{n})$
• 空間複雜度：$O(1)$