1. 题目：
给你一个按 非递减顺序 排序的整数数组 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]
2. 我的代码：
class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: result = [0] * len(nums) # 左右指针 left_i = 0 right_i = len(nums) - 1 # 给result赋值 while left_i <= right_i: if nums[left_i] ** 2 > nums[right_i] ** 2: result[right_i - left_i] = nums[left_i] ** 2 left_i += 1 else: result[right_i - left_i] = nums[right_i] ** 2 right_i -= 1 return result
有序数组的平方，这里的问题在于不能简单平方，因为-4的平方比3的平方大，会出现顺序的错乱。因此，我们想象一下y = x ^ 2的函数图像，越在两边的函数值越大。我们这时可能会想到，从值为0的地方开始，左右指针向两边扩散。
但是，index(0)的时间复杂度是n，因此可以选择，不过最好的选择还是从两边开始，向中间靠拢，这样就不需要查询0的位置了。
向中间靠拢需要比较两个元素的平方值，从而确定哪个先向中间移动一下。看代码即可，原理很简单。当然给新数组赋值是从后向前赋值的，对应的索引为：right_i - left_i
