有序数组的平方（LeetCode 977）

题目来源：LeetCode 977 · 有序数组的平方

题目

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

思路：两端夹击，从后往前填

平方会破坏升序（负数的平方可能很大），但抓住一个关键事实：平方后最大的数，只可能来自原数组的两端——绝对值越大平方越大，而两端正好是绝对值最大的位置。

1. 双指针 left、right 指向原数组两端
2. 比较 |nums[left]| 与 |nums[right]|，较大的那个平方后从后往前填入结果数组
3. 被选中的指针向内移动一步，重复直到两个指针交错

结果数组从后往前填，天然得到升序结果。

动画演示

代码

def sortedSquares(self, nums: List[int]) -> List[int]:
    left, right = 0, len(nums) - 1
    ans = [0] * len(nums)
    pos = right
    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            ans[pos] = nums[left] ** 2
            left += 1
        else:
            ans[pos] = nums[right] ** 2
            right -= 1
        pos -= 1
    return ans

边界：left == right 不能漏

数组长度为奇数时，两个指针最终会指向同一个元素：

• 它还没被平方过，必须处理——所以用 while left <= right（带等号），而不是 <
• 处理它时 left、right 指向同一格，abs 比较相等、选哪端结果都一样，平方后填入并双双收缩

用 while left < right 会漏掉正中间这一格，数组长度为奇数时答案少一个数。

复杂度

• 时间：O(n)，每轮处理一个元素，指针共移动 n 次
• 空间：O(1)，除结果数组外只用三个指针

其他边界

• 单元素数组：left == right 就是第一轮，直接平方返回
• 全负数组：绝对值随下标减小而增大，left 主导填充，结果仍升序
• 全非负数组：right 主导填充，平方后自然升序