Easy

题目描述

给你一个排序后的字符数组 letters，里面包含至少两个不同的字符，以及一个目标字符 target。

请你寻找 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^4
  • letters[i] 是小写英文字母
  • letters 按非递减顺序排列
  • letters 至少包含两个不同的字符
  • target 是小写英文字母

解题思路

这道题是一个典型的二分查找应用。由于数组已经排序，我们需要找到第一个大于目标字符的字符。

解题思路：

  1. 二分查找（推荐）：利用数组有序的特性，使用二分查找找到第一个大于 target 的字符。如果找不到，说明所有字符都小于等于 target，返回第一个字符。

  2. 线性搜索：直接遍历数组，找到第一个大于 target 的字符。

二分查找实现要点：

  • 使用标准的二分查找模板
  • 当 letters[mid] <= target 时，说明答案在右半部分
  • 当 letters[mid] > target 时，当前字符可能是答案，但还要看左半部分是否有更小的
  • 如果最终 left >= letters.length，说明没找到，返回 letters[0]

这种方法时间复杂度为 O(log n)，空间复杂度为 O(1)，是最优解法。

代码实现

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

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        left, right = 0, len(letters)
        
        while left < right:
            mid = (left + right) // 2
            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid
        
        return letters[0] if left == len(letters) else letters[left]

public class Solution {
    public char NextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.Length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (letters[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left == letters.Length ? letters[0] : letters[left];
    }
}

var nextGreatestLetter = function(letters, target) {
    let left = 0;
    let right = letters.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (letters[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left < letters.length ? letters[left] : letters[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度二分查找
时间复杂度O(log n)
空间复杂度O(1)

相关题目