当前位置：首页 > news >正文

LeetCode 744.寻找比目标字母大的最小字母：遍历或二分

news 2026/5/11 22:04:10

【LetMeFly】744.寻找比目标字母大的最小字母：遍历或二分

力扣题目链接：https://leetcode.cn/problems/find-smallest-letter-greater-than-target/

给你一个字符数组letters，该数组按非递减顺序排序，以及一个字符target。letters里至少有两个不同的字符。

返回letters中大于target的最小的字符。如果不存在这样的字符，则返回letters的第一个字符。

示例 1：

输入:letters = ['c', 'f', 'j']，target = 'a'输出:'c'解释：letters 中字典上比 'a' 大的最小字符是 'c'。

示例 2:

输入:letters = ['c','f','j'], target = 'c'输出:'f'解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。

示例 3:

输入:letters = ['x','x','y','y'], target = 'z'输出:'x'解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。

提示：

2 <= letters.length <= 10⁴
letters[i]是一个小写字母
letters按非递减顺序排序
letters最少包含两个不同的字母
target是一个小写字母

解题方法：二分或遍历

二分：二分查找第一个大于target的元素位置即可（upper_bound）

遍历：从头到尾遍历就好。

时间复杂度：二分O ( l o g n ) O(log n)O(logn)遍历O ( n ) O(n)O(n)
空间复杂度：O ( 1 ) O(1)O(1)

AC代码

C++和Python用的二分（因为调库很方便），Go、Java和Rust使用的遍历。

C++

/* * @LastEditTime: 2026-01-31 13:50:40 */classSolution{public:charnextGreatestLetter(vector<char>&letters,chartarget){vector<char>::iterator it=upper_bound(letters.begin(),letters.end(),target);returnit==letters.end()?letters[0]:*it;}};

Python

''' LastEditTime: 2026-01-31 13:56:59 '''fromtypingimportListfrombisectimportbisect_rightclassSolution:defnextGreatestLetter(self,letters:List[str],target:str)->str:idx=bisect_right(letters,target)returnletters[0]ifidx==len(letters)elseletters[idx]

Java

/* * @LastEditTime: 2026-01-31 14:01:16 */classSolution{publiccharnextGreatestLetter(char[]letters,chartarget){for(inti=0;i<letters.length;i++){if(letters[i]>target){returnletters[i];}}returnletters[0];}}

Go

/* * @LastEditTime: 2026-01-31 13:59:57 */packagemainfuncnextGreatestLetter(letters[]byte,targetbyte)byte{for_,c:=rangeletters{ifc>target{returnc}}returnletters[0]}

Rust

/* * @LastEditTime: 2026-01-31 14:03:50 */implSolution{pubfnnext_greatest_letter(letters:Vec<char>,target:char)->char{foriin0..letters.len(){ifletters[i]>target{returnletters[i];}}letters[0]}}