TNotes.leetcode

Appearance

0744. 寻找比目标字母大的最小字母【简单】

0744. 寻找比目标字母大的最小字母【简单】 ​

1. 📝 题目描述 ​

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

2. 🎯 s.1 - 二分查找（lower_bound + 环绕） ​

js
/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function (letters, target) {
  let l = 0
  let r = letters.length - 1

  // 二分查找：找到第一个严格大于 target 的位置
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    if (letters[mid] <= target) {
      // 当前字符 <= target，说明目标在右侧
      l = mid + 1
    } else {
      // 当前字符 > target，可能是答案，继续向左查找更小的
      r = mid - 1
    }
  }

  // l 最终指向第一个 > target 的位置
  // 如果 l 越界（等于 letters.length），说明没有更大的字符
  // 使用取模运算实现循环返回
  return letters[l % letters.length]
}
  • 时间复杂度：O(log⁡n)，每次将区间减半
  • 空间复杂度：O(1)

算法思路：

  • 在有序数组上二分，寻找第一个严格大于 target 的位置
  • 若 l < n，返回 letters[l]；否则按题意环绕返回 letters[0]
  • 可统一为返回 letters[l % n]（l 为二分结束后的左边界）

Discussions