LeetCode 977. 有序数组的平方

2026-01-19 HGNULB 约 5 分钟

文章信息 8 个分类 4 个标签

分类

题目描述

✅ 977. 有序数组的平方

题意分析

输入是一个按非递减顺序排好的整数数组，要求输出每个元素平方之后、仍然按非递减顺序排列的新数组。注意「非递减」允许相等元素相邻，也允许全部元素相同。

约束里最关键的信号是「输入已经有序」以及「元素可以是负数」。如果全是非负数，平方是单调递增的，直接逐个平方就已经有序，题目根本不成立；恰恰因为存在负数，平方把负半轴翻折了过来——原本最左边最小的负数，平方后可能变成整个数组里最大的。题目还给了进阶要求：不要直接排序，用 $O(n)$ 的方法解决，这等于明说「排序不是答案，要利用有序性」。

由此可以点明本题真正的题眼：平方后的最大值一定出现在原数组的两端。因为原数组有序，绝对值最大的元素只可能是最左端（最负的那个）或最右端（最正的那个），中间元素的绝对值不可能超过它们两个；而平方的大小完全由绝对值决定，所以最大的平方值必在这两端之一产生。这条性质是整个解法的地基。

边界上要考虑：数组可能只有一个元素；可能全为负数（此时结果是原数组平方后整体倒序）；可能全为非负数（此时结果就是逐个平方）；可能包含 0；也可能出现 -3 和 3 这种平方相等的对撞情形。

解法：双指针倒序填充

核心思路

平方会破坏负数部分原有的顺序，但平方值只由绝对值决定。对于任意尚未处理的有序区间 nums[left..right]，绝对值最大的元素一定在左右端点之一，因此当前最大的平方也只可能来自这两个位置。

用双指针夹住未处理区间，并让写指针 pos 从结果数组末尾向前移动。每轮比较两端的平方，把较大值写入 res[pos]，再收缩对应端点。这样先找到的最大值恰好放在最后，最终无需额外排序。

循环不变量：进入每一轮时，nums[left..right] 是尚未处理的元素，res[pos+1..n-1] 已经放好了所有已处理平方值，并且这些位置最终有序。每轮取出剩余区间的最大平方并放到最后一个空位，不变量继续成立；当 pos < 0 时，每个元素恰好处理一次，结果即为非递减序列。

解题步骤

创建长度为 n 的结果数组，令 left = 0、right = n - 1。

让 pos 从 n - 1 递减到 0，计算两端平方值。

将较大的平方写入 res[pos]，并移动产生该值的指针；两值相等时任选一端即可。

写满结果数组后返回。

例如 [-4,-1,0,3,10]：两端平方依次比较后，从后向前写入 100、16、9、1、0，最终得到 [0,1,9,16,100]。最后 left == right 时仍需处理一次，因此直接按 pos 循环最稳妥。

代码实现

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 0;
        int right = n - 1;
        for (int pos = n - 1; pos >= 0; pos--) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            if (leftSquare > rightSquare) {
                // 最大平方值放到当前最后的空位。
                res[pos] = leftSquare;
                left++;
            } else {
                res[pos] = rightSquare;
                right--;
            }
        }
        return res;
    }
}

func sortedSquares(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    left := 0
    right := n - 1
    for pos := n - 1; pos >= 0; pos-- {
        leftSquare := nums[left] * nums[left]
        rightSquare := nums[right] * nums[right]
        if leftSquare > rightSquare {
            // 原数组两端产生当前最大的平方值。
            res[pos] = leftSquare
            left++
        } else {
            res[pos] = rightSquare
            right--
        }
    }
    return res
}

复杂度分析

时间复杂度：$O(n)$，每个元素只被一个指针处理一次。

空间复杂度：$O(n)$，用于存放返回结果；若不计返回数组，辅助空间为 $O(1)$。

关键点总结

有序数组中绝对值最大者一定在区间两端，这是使用双指针的依据。

每轮先得到最大平方，所以必须从结果末尾向前填。

用写指针控制固定的 n 轮，能自然覆盖双指针相遇时的最后一个元素。

面试时应能解释：平方后负数段次序反转，直接逐项平方不再有序；双指针利用原有顺序把排序的 $O(n \log n)$ 降为 $O(n)$。

易错点总结

比较原值而非平方（或绝对值），会在左端负数绝对值更大时选错。

从前向后写入较大值，会得到降序结果。

当两端平方相等时同时移动两个指针，只填一个位置却丢掉一个元素；每轮只能消费一端。

用 left < right 作为循环条件会漏掉相遇位置；按 pos >= 0 固定执行 n 轮更直接。

若题目扩大元素范围，平方可能溢出 int；本题最大平方为 $10^8$，使用 int 安全。

相似题目

题目	难度	考察点
88. 合并两个有序数组	简单	从后往前归并避免覆盖
167. 两数之和 II - 输入有序数组	中等	有序数组上的对撞双指针
26. 删除有序数组中的重复项	简单	同向快慢指针原地去重
283. 移动零	简单	原地搬移并保持相对顺序
75. 颜色分类	中等	三指针一趟完成三路划分
844. 比较含退格的字符串	简单	双串各自从尾部回溯比较