题目重点：代入 ax²+bx+c 后不直接再排序，利用抛物线两端极值按 a 的符号从外向内填充。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入升序整数数组，可重复；a、b、c 为整数，输出升序。训练代码使用 Python 无限精度整数；固定字长语言应评估 ax² 溢出。
解题路线
- 二次函数 a>0 时开口向上，输入区间两端中的较大变换值是剩余区间的最大值；用左右指针比较两端，较大者从结果末尾向前填。
- a<0 时开口向下，剩余最小变换值在两端；比较两端较小者，从结果头部向后填。a=0 是单调线性函数，a≥0 的端点最大值倒序填法仍适用。
- 每轮消费一个端点，剩余输入仍是连续有序区间，归纳保证当前选出的极值放在正确输出位置。
- 直接映射再排序 O(N log N) 是可读基线；若长度很短或面试无性能要求，先给基线并解释线性优化。
手动走一遍
A=[-4,-2,2,4]、f(x)=x²：两端 16/16 先填末尾，再 4/4，结果 [4,4,16,16]。若 f(x)=−x²，则两端先给最小的 −16，结果 [−16,−16,−4,−4]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def sorted_quadratic(values: list[int], a: int, b: int, c: int) -> list[int]:
n = len(values)
result = [0] * n
left, right = 0, n - 1
write = n - 1 if a >= 0 else 0
step = -1 if a >= 0 else 1
def f(x):
return a * x * x + b * x + c
while left <= right:
lv, rv = f(values[left]), f(values[right])
if a >= 0:
if lv >= rv:
result[write] = lv
left += 1
else:
result[write] = rv
right -= 1
else:
if lv <= rv:
result[write] = lv
left += 1
else:
result[write] = rv
right -= 1
write += step
return result
复杂度
O(N) 时间、O(N) 输出空间，额外指针 O(1)。30,000 组随机数组及系数与独立映射排序结果一致。
易错点与追问
容易失分的边界
- a<0 仍按较大端点倒序填。
- 以顶点为界分别排序两半，增加不必要成本。
- a=0 且 b<0 时误以为输出保持输入顺序。
- 两个端点相等时双消费，导致漏元素。
- 固定宽整数计算 x² 溢出。
继续深挖
- a=0 时结果方向怎么判断？
- 如果输入是降序如何改？
- 大量重复值对算法有影响吗？
- 函数改成三次多项式还能两指针吗？
