Jianbo Dai's

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

 
  • Sep 26, 2021

题目链接

刷了一波二分，都是最简单的那种找>=value的下界，所以没来记录，这个题稍微有点变化，找的是>=value的上界，这个可以转化成找>=(value+1)的下界，就一样容易了。不赘述。这个算法的时间复杂度是O（logN），空间复杂度是O（1）。

python:

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        first, last = 0, len(letters)
        res = self.helper(letters, first, last, target)
        return letters[res] if res < len(letters) else letters[0]

    def helper(self, letters, first, last, target):
        target = chr(ord(target) + 1)
        while first < last:
            mid = first + (last - first) // 2
            if letters[mid] == target:
                return mid
            elif letters[mid] < target:
                first = mid + 1
            else:
                last = mid
        return first
Search