977.有序数组的平方

版本一）双指针法
class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:l, r, i = 0, len(nums)-1, len(nums)-1res = [float('inf')] * len(nums) # 需要提前定义列表，存放结果while l <= r:if nums[l] ** 2 < nums[r] ** 2: # 左右边界进行对比，找出最大值res[i] = nums[r] ** 2r -= 1 # 右指针往左移动else:res[i] = nums[l] ** 2l += 1 # 左指针往右移动i -= 1 # 存放结果的指针需要往前平移一位return res

代码解释：有序数组的平方（Squares of a Sorted Array）

这段代码用于将一个 非递减排序的整数数组 nums（可能包含负数）中的每个元素平方后，返回一个新的 非递减排序的数组。 关键点：

• 利用原数组已排序的特性：最大的平方值一定出现在数组的两端（最左或最右）。
• 双指针法：从数组两端向中间遍历，比较平方值，将较大的放入结果数组的末尾。

变量说明

变量	作用	初始值
l	左指针（从数组头部开始）	0
r	右指针（从数组尾部开始）	len(nums) - 1
i	结果数组的填充位置（从末尾开始）	len(nums) - 1
res	存储结果的数组	[float('inf')] * len(nums)

算法流程

1. 初始化：

   • 左指针 l = 0，右指针 r = len(nums) - 1。
   • 结果数组 res 初始化为长度与 nums 相同的数组，填充 float('inf')（表示正无穷，仅占位用）。

2. 循环条件：while l <= r（左右指针未相遇时继续）。

3. 比较平方值：

   • 如果 nums[l]² < nums[r]²：
     • 将 nums[r]² 存入 res[i]。
     • 右指针左移（r -= 1）。
   • 否则：
     • 将 nums[l]² 存入 res[i]。
     • 左指针右移（l += 1）。
   • 结果数组的填充位置 i 左移（i -= 1）。

4. 返回结果：res 即为平方后的有序数组。

具体例子

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

执行过程：

1. 初始状态：

   • nums = [-4, -1, 0, 3, 10]
   • l = 0, r = 4, i = 4
   • res = [inf, inf, inf, inf, inf]

2. 第 1 轮循环：

   • nums[0]² = 16, nums[4]² = 100
   • 16 < 100 → res[4] = 100, r = 3, i = 3
   • res = [inf, inf, inf, inf, 100]

3. 第 2 轮循环：

   • nums[0]² = 16, nums[3]² = 9
   • 16 > 9 → res[3] = 16, l = 1, i = 2
   • res = [inf, inf, inf, 16, 100]

4. 第 3 轮循环：

   • nums[1]² = 1, nums[3]² = 9
   • 1 < 9 → res[2] = 9, r = 2, i = 1
   • res = [inf, inf, 9, 16, 100]

5. 第 4 轮循环：

   • nums[1]² = 1, nums[2]² = 0
   • 1 > 0 → res[1] = 1, l = 2, i = 0
   • res = [inf, 1, 9, 16, 100]

6. 第 5 轮循环：

   • nums[2]² = 0, nums[2]² = 0
   • 0 == 0 → res[0] = 0, l = 3, i = -1
   • res = [0, 1, 9, 16, 100]

7. 循环结束（l > r）：

   • 最终 res = [0, 1, 9, 16, 100]。

结果：

• 平方后的有序数组：[0, 1, 9, 16, 100]。

示例 2：nums = [-7, -3, 2, 3, 11]

执行过程：

1. 初始状态：

   • nums = [-7, -3, 2, 3, 11]
   • l = 0, r = 4, i = 4
   • res = [inf, inf, inf, inf, inf]

2. 循环过程：

   • fast=0: nums[0]²=49, nums[4]²=121 → res[4]=121, r=3, i=3
   • fast=1: nums[0]²=49, nums[3]²=9 → res[3]=49, l=1, i=2
   • fast=2: nums[1]²=9, nums[3]²=9 → res[2]=9, r=2, i=1
   • fast=3: nums[1]²=9, nums[2]²=4 → res[1]=9, l=2, i=0
   • fast=4: nums[2]²=4, nums[2]²=4 → res[0]=4, l=3, i=-1

3. 结果：

   • res = [4, 9, 9, 49, 121]。

为什么用 float('inf') 初始化 res？

• 仅占位作用：表示未填充的位置，实际会被覆盖。
• 可替换为其他值：例如 0 或 None，不影响逻辑。