🔍 初学者友好指南 ‘查找大于目标的最小字母’ - Problem 744 (C++, Python, JavaScript)

Source: Dev.to

问题概述

给定：

• 一个已排序的字符列表 letters。
• 一个特定的字符 target。

你的目标：

• 找到列表中严格大于 target 的最小字符。
• 如果不存在这样的字符（即 target 大于或等于列表中的每个元素），返回列表中的第一个字符。

直觉

因为数组已经排好序，我们可以避免线性扫描（ O(n) ），而改用二分查找（ O(log n) ）。

算法遵循“搜索并丢弃”的思路：

1. 检查中间元素。
2. 如果 letters[mid] > target – 这可能是答案。记录下索引并继续在 左半部分 搜索更小的符合条件的字符。
3. 如果 letters[mid] ≤ target – 中间元素及其左侧的所有元素都太小。丢弃它们，搜索 右半部分。

如果搜索结束仍未找到更大的字符，我们“环绕”返回 letters[0]。

步骤演示：理解示例

示例 1

letters = ["c", "f", "j"], target = "a"

大于 'a' 的第一个字符是 'c'。

结果： "c"

示例 2

letters = ["c", "f", "j"], target = "c"

'c' 不符合要求，因为我们需要严格更大的字符。下一个是 'f'。

结果： "f"

示例 3

letters = ["x", "x", "y", "y"], target = "z"

没有字符大于 'z'；我们循环回到第一个元素。

结果： "x"

代码实现

C++

class Solution {
public:
    char nextGreatestLetter(vector& letters, char target) {
        int n = letters.size();
        int left = 0;
        int right = n - 1;
        int firstTrueIndex = -1;

        while (left  target) {
                firstTrueIndex = mid;
                right = mid - 1;          // look for a smaller qualifying character
            } else {
                left = mid + 1;           // discard left half
            }
        }

        return firstTrueIndex == -1 ? letters[0] : letters[firstTrueIndex];
    }
};

Python

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        n = len(letters)
        left, right = 0, n - 1
        first_true_index = -1

        while left  target:
                first_true_index = mid
                right = mid - 1
            else:
                left = mid + 1

        return letters[0] if first_true_index == -1 else letters[first_true_index]

JavaScript

/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function (letters, target) {
    let left = 0;
    let right = letters.length - 1;
    let firstTrueIndex = -1;

    while (left  target) {
            firstTrueIndex = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return firstTrueIndex === -1 ? letters[0] : letters[firstTrueIndex];
};

关键要点

• 二分查找效率： 每次迭代将搜索空间减半，使时间复杂度达到 O(log n)，而不是 O(n)。
• 上界模式： 该问题是经典的“上界”搜索——寻找第一个严格大于给定值的元素。
• 环绕处理： 使用哨兵值（例如 firstTrueIndex = -1）或模运算提供了一种简洁的实现循环数组逻辑的方法。

Final Thoughts

这个问题是优化搜索功能的绝佳入门。real‑world 系统，例如文件资源管理器或联系人列表，常常需要在用户输入字符时跳转到“下一个更大的”条目。掌握 binary search 不仅为顶级科技公司的技术面试做好准备，也使你能够编写能够扩展到数百万条目的高性能代码。