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=0for i in nums:j=i*inums_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=0for i in nums:j=i*inums_sq.append(j)nums_sq.sort()return nums_sq

題目允許調用函數，可以不手寫排序，節省時間。

最優版：

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:n = len(nums)result = [0] * nleft, right = 0, n - 1pos = n - 1while left <= right:if abs(nums[left]) > abs(nums[right]):result[pos] = nums[left] ** 2left += 1else:result[pos] = nums[right] ** 2right -= 1pos -= 1return result

雙指針法：
雙指針從兩端找平方最大值，逆序填入新數組。
1、為何逆序插入？
我們從數組兩端找最大平方值，大的數應該放在結果數組的最后面，所以我們需要從后往前插入。
最大平方值一定出現在原數組的兩端。設置雙指針從兩端開始比較
創建一個結果數組 result，長度相同，全部初始化為 0。—>result=[0]*n

大致思路：
比較兩端絕對值大小：
誰的絕對值大，說明平方后也更大；
將較大的平方放入結果數組的最后一個位置；
創建左右指針：left 指向最左，right 指向最右；移動對應指針（左邊大就 left += 1，右邊大就 right -= 1）；
重復上述過程，直到左右指針相遇。