难度: Easy
给你一个按 非递减顺序 排序的整数数组 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 <= 104-104 <= nums[i] <= 104nums 已按 非递减顺序 排序
进阶：
O(n) 的算法解决本问题运行时间: 28 ms
内存: 18.4 MB
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
index=len(nums)-1
right=len(nums)-1
left=0
tmp = [None]*len(nums)
while(left<=right):
if(nums[left]*nums[left]>nums[right]*nums[right]):
tmp[index] = nums[left]*nums[left]
left = left+1
index = index-1
else:
tmp[index] = nums[right]*nums[right]
right = right-1
index = index-1
return tmp
题解采用了双指针技术来解决问题。数组`nums`已经是非递减排序的，但平方后的值可能改变元素的相对顺序，特别是负数的平方可能变得比原有的正数大。解决方案中，使用了两个指针`left`和`right`分别指向数组的开头和结尾。一个辅助数组`tmp`被用来从后向前填充结果，以保证平方后也是非递减顺序。每次比较`left`和`right`处的数的平方，将较大的平方数放入`tmp`中，并移动相应的指针，直到所有元素都处理完毕。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
index = len(nums) - 1 # 结果数组的填充起始位置
right = len(nums) - 1 # 右指针，从数组末尾开始
left = 0 # 左指针，从数组开头开始
tmp = [None] * len(nums) # 创建一个和nums长度相同的数组
while (left <= right):
if (nums[left] * nums[left] > nums[right] * nums[right]):
tmp[index] = nums[left] * nums[left] # 如果左边的平方大，则填充到tmp中，并移动左指针
left += 1
else:
tmp[index] = nums[right] * nums[right] # 否则填充右边的平方，并移动右指针
right -= 1
index -= 1 # 更新填充位置
return tmp # 返回结果数组
在这个问题中，主要考虑的是平方后值的大小和排序。由于输入数组是非递减的，数组两端的值的绝对值往往是最大的，尤其是当包含负数时。从两端开始可以直接比较两端数的平方，直接决定哪个数的平方应该放在结果数组的末尾。如果从中间开始向两边扩展，虽然中间的数平方后可能小，但需要额外的逻辑来确定每个平方值的正确位置，这会增加算法的复杂性和执行时间。
当左右指针指向的数的平方相等时，选择移动哪一个指针实际上并不会影响最终结果的排序，因为相等的平方值填入结果数组的顺序并不影响结果数组的非递减属性。在解决方案中可以选择移动任一指针，通常出于简化代码的考虑，可以优先移动右指针（或左指针），这样做主要是为了保持代码的一致性和可读性。
数组`tmp`是从后向前填充的，始终将当前最大的平方数放在数组的后部未填充的最前面。由于`nums`数组是非递减的，其平方后的最大值一定出现在原数组的两端。通过比较两端的平方，可以确保每次填充的都是目前未处理的最大平方数，保持`tmp`数组的非递减顺序。即使存在重复元素，只要按照这种方法填充，就能确保填充过程中的顺序性，因为相同的数平方后仍然相同，填充顺序不影响最终结果的顺序。
对于只有一个元素的数组，由于双指针`left`和`right`初始化时指向同一个位置，循环会正常执行一次，正确地计算出这个元素的平方并填充到`tmp`数组中，返回的结果也会是正确的。如果所有元素都是负数，这些元素的平方会变成正数，由于原数组是非递减的，平方后的数组实际上应该是非递增的。但是由于我们从两端向中心比较并填充，所以最大的平方数（位于原数组左端的数的平方）会首先被处理，保证了`tmp`数组填充的非递减顺序。