【Leetcode Daily】744寻找比目标字母大的最小字母

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个非递减顺序的字符数组，和一个字符 target，求数组中字典序大于 target 字符中最小的字符。

思路分享

• 解决三个问题就能做出本题，1. 二分怎么写；2. 怎么找二分目标值的后一个（前一个同理）；3. 如何正确检查目标字符是否存在；

• 前两个问题在 【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置 中已说明，第三个问题在 【Leetcode Daily】704二分查找也有所说明。

代码解答（强烈建议自行解答后再看）

• 参考题解

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