有序数组的平方

给你一个按非递减顺序排序的整数数组 nums，请返回每个数字的平方组成的新数组，要求返回结果也按非递减顺序排序。

题目描述

示例 1：

Text
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后数组变为 [16,1,0,9,100]，排序后得到 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

核心观察

原数组已经有序，但平方之后不一定有序，因为负数平方后可能变得很大。

例如：

原数组：[-4, -1, 0, 3, 10]
平方后：[16, 1, 0, 9, 100]

关键点是：

原数组越靠近两端，绝对值越可能大；
平方后的最大值一定出现在当前区间的左端或右端；
因此可以用两个指针分别指向数组两端，每次取平方更大的那个数放到结果数组的末尾。

配图 TODO

这里建议补一张图：左指针指向数组开头，右指针指向数组末尾，结果数组从右往左填充。每一步比较 nums[left]² 和 nums[right]²，把较大值放到 res[k]。

解法一：暴力排序

最直接的做法是先把每个元素平方，再排序。

暴力排序
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            nums[i] *= nums[i];
        }

        sort(nums.begin(), nums.end());
        return nums;
    }
};

复杂度分析：

指标	复杂度	说明
时间复杂度	$O(n \log n)$	平方是 $O(n)$ ，排序是 $O(n \log n)$
空间复杂度	$O(1)$ 或 $O(\log n)$	取决于排序实现的额外栈空间

暴力排序能过，但没有利用“原数组已经有序”这个条件。

解法二：双指针

设：

left 指向当前区间最左端；
right 指向当前区间最右端；
k 指向结果数组当前要填写的位置，从最后一个位置开始。

每一轮比较：

nums[left] * nums[left] 与 nums[right] * nums[right]

谁更大，就把谁放到 res[k]，然后对应指针向中间移动，同时 k--。

这样做的原因是：结果数组需要从小到大排列，而我们每次取到的是当前最大平方值，所以应该从结果数组尾部往前填。

双指针：从后向前填充
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 0);

        int left = 0;
        int right = n - 1;
        int k = n - 1;

        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];

            if (leftSquare > rightSquare) {
                res[k--] = leftSquare;
                left++;
            } else {
                res[k--] = rightSquare;
                right--;
            }
        }

        return res;
    }
};

复杂度分析：

指标	复杂度	说明
时间复杂度	$O(n)$	每个元素只会被左右指针访问一次
空间复杂度	$O(n)$	需要一个结果数组保存答案

为什么不是从前往后填？

如果从前往后填，就要每次找当前最小平方值。但对于一个有负数和正数混合的有序数组，最小平方值通常在中间附近，不容易直接用两端指针确定。

从后往前填则非常自然：当前最大平方值一定在两端。

手动模拟

以 nums = [-4, -1, 0, 3, 10] 为例：

轮次	`left` 指向	`right` 指向	较大平方	填入位置	`res` 当前状态
1	-4	10	100	4	`[0,0,0,0,100]`
2	-4	3	16	3	`[0,0,0,16,100]`
3	-1	3	9	2	`[0,0,9,16,100]`
4	-1	0	1	1	`[0,1,9,16,100]`
5	0	0	0	0	`[0,1,9,16,100]`

易错点

循环条件应为 left <= right，因为当两个指针相遇时，最后一个元素仍然需要处理。
结果数组要从后往前填，不能从前往后填。
比较的是平方值，不是原值。
平方可能溢出时，要根据题目数据范围判断是否需要更大整数类型。本题使用 int 足够。

代码模板

C++
Java
Python
JavaScript
TypeScript

C++
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);

        int left = 0;
        int right = n - 1;
        int k = n - 1;

        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];

            if (leftSquare > rightSquare) {
                res[k--] = leftSquare;
                left++;
            } else {
                res[k--] = rightSquare;
                right--;
            }
        }

        return res;
    }
};

Java
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];

        int left = 0;
        int right = n - 1;
        int k = n - 1;

        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];

            if (leftSquare > rightSquare) {
                res[k--] = leftSquare;
                left++;
            } else {
                res[k--] = rightSquare;
                right--;
            }
        }

        return res;
    }
}

Python
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n

        left, right = 0, n - 1
        k = n - 1

        while left <= right:
            left_square = nums[left] * nums[left]
            right_square = nums[right] * nums[right]

            if left_square > right_square:
                res[k] = left_square
                left += 1
            else:
                res[k] = right_square
                right -= 1
            k -= 1

        return res

JavaScript
var sortedSquares = function(nums) {
    const n = nums.length;
    const res = new Array(n).fill(0);

    let left = 0;
    let right = n - 1;
    let k = n - 1;

    while (left <= right) {
        const leftSquare = nums[left] * nums[left];
        const rightSquare = nums[right] * nums[right];

        if (leftSquare > rightSquare) {
            res[k--] = leftSquare;
            left++;
        } else {
            res[k--] = rightSquare;
            right--;
        }
    }

    return res;
};

TypeScript
function sortedSquares(nums: number[]): number[] {
    const n = nums.length;
    const res: number[] = new Array(n).fill(0);

    let left = 0;
    let right = n - 1;
    let k = n - 1;

    while (left <= right) {
        const leftSquare = nums[left] * nums[left];
        const rightSquare = nums[right] * nums[right];

        if (leftSquare > rightSquare) {
            res[k--] = leftSquare;
            left++;
        } else {
            res[k--] = rightSquare;
            right--;
        }
    }

    return res;
}

总结

这道题的核心不是“平方后排序”，而是要利用原数组已经有序的性质。

当数组有序时，平方后的最大值一定来自当前左右两端。因此，用双指针从两端向中间扫描，再从结果数组末尾往前填，就可以把时间复杂度从 $O(n \log n)$ 优化到 $O(n)$ 。

题目描述​

核心观察​

解法一：暴力排序​

解法二：双指针​

手动模拟​

易错点​

代码模板​

总结​