力扣刷题977——有序数组的平方

977. 有序数组的平方

题目：

给你一个按 非递减顺序 排序的整数数组 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]

出版作答（python3）:

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        nums_sq=[]
        n=0
        for i in nums:
            j=i*i
            nums_sq.append(j)
        n = len(nums_sq)
        for i in range(n):
            for j in range(0, n - i - 1):
                if nums_sq[j] > nums_sq[j + 1]:
                    nums_sq[j], nums_sq[j + 1] = nums_sq[j + 1], nums_sq[j]
        return nums_sq

提交的时候超出时间限制。先平方，之后采用手动的冒泡排序，超时。

第二版：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        nums_sq=[]
        n=0
        for i in nums:
            j=i*i
            nums_sq.append(j)
        nums_sq.sort()
        return nums_sq

题目允许调用函数，可以不手写排序，节省时间。

最优版：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left, right = 0, n - 1
        pos = n - 1

        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                result[pos] = nums[left] ** 2
                left += 1
            else:
                result[pos] = nums[right] ** 2
                right -= 1
            pos -= 1

        return result

双指针法：
双指针从两端找平方最大值，逆序填入新数组。
1、为何逆序插入？
我们从数组两端找最大平方值，大的数应该放在结果数组的最后面，所以我们需要从后往前插入。
最大平方值一定出现在原数组的两端。设置双指针从两端开始比较
创建一个结果数组 result，长度相同，全部初始化为 0。—>result=[0]*n

大致思路：
比较两端绝对值大小：
谁的绝对值大，说明平方后也更大；
将较大的平方放入结果数组的最后一个位置；
创建左右指针：left 指向最左，right 指向最右；移动对应指针（左边大就 left += 1，右边大就 right -= 1）；
重复上述过程，直到左右指针相遇。