977. 有序数组的平方

题目

力扣题目

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

示例 1：

输入：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]

提示：

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按非递减顺序排序

进阶：请设计时间复杂度为 $O(n)$ 的算法解决本问题。

考察内容

• 有序数组的性质
• 相向双指针
• 从结果数组末尾逆序填充
• 时间复杂度与空间复杂度分析

解题思路

直接平方后排序

先将每个元素平方，再对结果数组排序。这种方法容易实现，但排序需要 $O(n\log n)$ 的时间，没有利用原数组已经有序这一条件。

相向双指针

数组虽然按数值升序排列，但平方之后的最大值不一定在原数组右侧。例如 -4 的平方大于 3 的平方。

对于一个有序数组，绝对值最大的元素一定出现在当前区间的两端。因此可以设置两个指针：

• left 指向当前区间最左侧；
• right 指向当前区间最右侧；
• write 指向结果数组当前需要填写的位置，从末尾向前移动。

每轮比较 nums[left]² 和 nums[right]²，把较大的平方放入 result[write]，然后移动对应的指针。这样可以保证结果数组从大到小被填入，最终整体呈非递减顺序。

循环不变量是：result[write + 1, n) 已经放好了最大的若干个平方值，并且位置正确。

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

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$，用于存放返回结果

代码演示

std::vector<int> sortedSquares(std::vector<int>& nums) {
    std::vector<int> result(nums.size());
    
    int left  = 0;
    int right = nums.size() - 1;
    int pos = right;

    while (left <= right) {
        int left_square = nums[left] * nums[left];
        int right_square = nums[right] * nums[right];

        if (left_square > right_square) {
            result[pos--] = left_square;
            ++left;
        } else {
            result[pos--] = right_square;
            --right;
        }
    }

    return result;
}

易错点

• 直接从前向后填结果：两端元素平方后都可能成为最大值，应该从结果数组末尾开始填充。
• 循环条件写成 left < right：当两个指针相遇时还有一个元素没有处理，因此应使用 left <= right。
• 移动了错误的指针：选择左端平方后移动 left，选择右端平方后移动 right。
• 只比较原值大小：应该比较平方值或绝对值，而不是直接比较 nums[left] 与 nums[right]。
• 忘记原数组可能全为负数或全为正数：相向双指针写法能够统一处理这些情况，不需要单独分支。
• 整数溢出：本题约束下平方最大为 $10^8$，int 足够；如果输入范围更大，应使用 long long。

总结

本题的关键是观察到：有序数组平方后的最大值只可能来自当前区间的左右两端。使用相向双指针选择较大的平方，并从结果数组末尾向前填写，可以在线性时间内完成排序。

• 读取顺序：从数组两端向中间；
• 写入顺序：从结果末尾向开头；
• 时间复杂度：$O(n)$；
• 空间复杂度：$O(n)$。

相关题目

• 27. 移除元素
• 88. 合并两个有序数组
• 167. 两数之和 II - 输入有序数组
• 283. 移动零
• 844. 比较含退格的字符串