Uber 有序数组平方：全排序、最小 k 个与第 k 大

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入非递减整数数组，允许负数、零、重复值。基础输出是所有平方值的非递减序列。
• 第 k 大使用 1-based k；最小 k 个按非递减顺序返回且 k 可以为 0。两种追问分别对应不同题目，不把第 k 大与最小 k 个混为同一个输出。
• Python 可用任意精度整数；定长整数语言平方前需处理乘法溢出。

解题路线

1. 完整排序：平方最大值一定来自输入左端最负或右端最大。双指针比较两端绝对值，把较大的平方从结果末端向前填，O(n)。
2. 最小 k 个：二分找到第一个非负值的位置，零点左侧的绝对值按逆向递增，右侧按正向递增；合并这两个有序流直到输出 k 项，O(log n+k)。
3. 第 k 大：已得到完整有序平方数组时直接取下标 n−k；若只问一次且 k 很小，可从两端每次抽当前最大，共 O(k)，但重复查询更适合预处理。

手动走一遍

输入 [-4,-1,0,3,3]，平方有序结果 [0,1,9,9,16]；最小 3 个为 [0,1,9]，第 2 大为 9。直接按原数组顺序平方得到 [16,1,0,9,9]，仍未排序。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Sorted squares plus k-smallest and kth-largest variants."""

from bisect import bisect_left


def sorted_squares(values: list[int]) -> list[int]:
    if any(a > b for a, b in zip(values, values[1:])):
        raise ValueError("input must be sorted")
    left, right = 0, len(values) - 1
    result = [0] * len(values)
    for write in range(len(values) - 1, -1, -1):
        if abs(values[left]) > abs(values[right]):
            result[write] = values[left] ** 2
            left += 1
        else:
            result[write] = values[right] ** 2
            right -= 1
    return result


def smallest_k_squares(values: list[int], k: int) -> list[int]:
    if not 0 <= k <= len(values):
        raise ValueError("k outside array")
    if any(a > b for a, b in zip(values, values[1:])):
        raise ValueError("input must be sorted")
    right = bisect_left(values, 0)
    left = right - 1
    result = []
    for _ in range(k):
        if right == len(values) or (left >= 0 and abs(values[left]) <= abs(values[right])):
            result.append(values[left] ** 2)
            left -= 1
        else:
            result.append(values[right] ** 2)
            right += 1
    return result


def kth_largest_square(values: list[int], k: int) -> int:
    if not 1 <= k <= len(values):
        raise ValueError("k must be 1..n")
    squares = sorted_squares(values)
    return squares[-k]

复杂度

完整有序平方 O(n) 时间与 O(n) 输出空间；最小 k 个为二分 O(log n) 加双流合并 O(k) 时间、O(k) 输出空间；第 k 大示例代码复用完整排序 O(n)。

易错点与追问

容易失分的边界

• 原数组按值有序，不代表平方后仍有序；负数绝对值需要从左端读取。
• 零点二分后左指针往左走、右指针往右走，才能各自保持平方值非递减。
• 题目有人提用 binary search 求最小 k 个，二分只负责定位零点；不能仅靠一次二分给出全部 k 个输出。

继续深挖

• 若输入数据量无法全放内存，可从两端顺序访问时分块生成倒序最大值或围绕零点进行双流合并，但需要支持合适的双向/索引访问。
• 若要 kth largest 而不构建完整结果，可用两端指针跳过前 k−1 个最大平方，时间 O(k)、辅助空间 O(1)。