leetcode代码记录（有序数组的平方

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