動機
複習upper bound
Problem
Given a characters array letters
that is sorted in non-decreasing order and a character target
, return the smallest character in the array that is larger than target
.
Note that the letters wrap around.
- For example, if
target == 'z'
andletters == ['a', 'b']
, the answer is'a'
.
Example 1:
Input: letters = [c,f,j], target = aOutput: c
Example 2:
Input: letters = [c,f,j], target = cOutput: f
Example 3:
Input: letters = [c,f,j], target = dOutput: f
Example 4:
Input: letters = [c,f,j], target = gOutput: j
Example 5:
Input: letters = [c,f,j], target = jOutput: c
Constraints:
2 <= letters.length <= 104
letters[i]
is a lowercase English letter.letters
is sorted in non-decreasing order.letters
contains at least two different characters.target
is a lowercase English letter.
Sol
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
i = bisect_right(letters, target)
return letters[i] if i < len(letters) else letters[0]