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

【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 <= 104
• letters[i] 是一个小写字母
• letters 按非递减顺序排序
• letters 最少包含两个不同的字母
• target 是一个小写字母

解题方法：二分或遍历

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

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

• 时间复杂度：二分$O(log n)$遍历$O(n)$
• 空间复杂度：$O(1)$

AC代码

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

C++

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

Python

'''
LastEditTime: 2026-01-31 13:56:59
'''
from typing import List
from bisect import bisect_right

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        idx = bisect_right(letters, target)
        return letters[0] if idx == len(letters) else letters[idx]

Java

/*
 * @LastEditTime: 2026-01-31 14:01:16
 */
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        for (int i = 0; i < letters.length; i++) {
            if (letters[i] > target) {
                return letters[i];
            }
        }
        return letters[0];
    }
}

Go

/*
 * @LastEditTime: 2026-01-31 13:59:57
 */
package main

func nextGreatestLetter(letters []byte, target byte) byte {
    for _, c := range letters {
        if c > target {
            return c
        }
    }
    return letters[0]
}

Rust

/*
 * @LastEditTime: 2026-01-31 14:03:50
 */
impl Solution {
    pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char {
        for i in 0..letters.len() {
            if letters[i] > target {
                return letters[i];
            }
        }
        letters[0]
    }
}

• 执行用时分布0ms击败100.00%
• 消耗内存分布2.72MB击败97.14%

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源