力扣数组
977. 有序数组的平方
977. 有序数组的平方
https://leetcode.cn/problems/squares-of-a-sorted-array
题目
给你一个按 非递减顺序 排序的整数数组 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⁴
- -10⁴ <= nums[i] <= 10⁴
- nums 已按 非递减顺序 排序
思路
核心逻辑：利用原数组「非递减」的特性，平方后的最大值必然出现在数组两端（负数绝对值越大平方越大，正数越大平方越大）。通过三个指针实现高效填充：
- 左指针
left指向数组头部，右指针right指向数组尾部，分别代表当前待比较的两端元素； - 结果指针
i指向结果数组的尾部，代表当前需要填充的位置； - 比较
left和right对应元素的平方值，将较大值放入res[i]，并移动对应指针（left右移 /right左移），同时i左移； - 循环直到
left > right（所有元素处理完毕），结果数组即为非递减的平方数组。
解法
nums = [-4,-1,0,3,10]
def sortedSquares(nums: list[int]) -> list[int]:
n = len(nums)
left, right, i = 0, n - 1, n - 1
res = [0] * n
while left <= right:
left_sq = nums[left] ** 2
right_sq = nums[right] ** 2
if left_sq > right_sq:
res[i] = left_sq
left += 1
else:
res[i] = right_sq
right -= 1
i -= 1
return res
print(sortedSquares(nums)) # 输出：[0,1,9,16,100]解释
| 代码片段 | 作用与原因 |
|---|---|
left, right, i = 0, n - 1, n - 1 | 初始化指针：left/right 覆盖原数组两端，i 从结果数组尾部开始填充（先放最大值） |
res = [0] * n | 预先初始化固定长度的结果数组，避免动态扩容，空间复杂度 O(n) |
while left <= right | 循环条件：只要左右指针未交叉，说明还有元素未处理（left==right 时处理最后一个元素） |
left_sq = nums[left] ** 2 / right_sq = nums[right] ** 2 | 计算两端元素平方，避免重复计算，命名更语义化 |
res[i] = left_sq + left += 1 | 左指针元素平方更大，将其放入当前结果位置，左指针右移缩小范围 |
res[i] = right_sq + right -= 1 | 右指针元素平方更大/相等，将其放入当前结果位置，右指针左移缩小范围 |
i -= 1 | 结果指针左移，准备接收下一个次大值，保证结果数组非递减 |