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

发布时间 2023-04-19 20:56:08作者: 风乐

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

简单二分,需要注意的是此题的二分check条件if(letters[mid]>target),这里的大于号是不能为大于等于的

若等于,则最后的l或r下标就会可能出现

1.nums[l]=target

2.target比序列所有都小,那么l或r为第一个元素索引,即0

此时就需要额外判断来return letters[l+1]还是return letters[l]

或者可以采取更简单更直接的办法,check条件可以为

if(leeters[mid]<=target) l=mid+1;
else r=mid;

如此更新后的l或r就是大于target的第一个元素下标或者是第一个元素0

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int l=0,r=letters.size()-1;
        if(target>=letters[r])return letters[0];
        while(l<r)
        {
            int mid=l+r>>1;
            if(letters[mid]>target)r=mid;
            else l=mid+1;
        }
        return letters[l];
    }
};