[LeetCode][Python]977. 有序数组的平方

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

一开始也是没有什么思路，连排序都没想到，后来参考了一下专家的解法，豁然开朗

方法一：排序
思路与算法

创建一个新的数组，它每个元素是给定数组对应位置元素的平方，然后排序这个数组。这对于Python比较方便，它有自带的sort方法

方法二：双指针
思路
因为数组 A 已经排好序了， 所以可以说数组中的负数已经按照平方值降序排好了，数组中的非负数已经按照平方值升序排好了。

算法

首先，确定正值和负值临界点，然后正值部分向尾部走，负值部分向头部走。接下来就是比较数字平方的大小，依次放入一个空列表

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        N = len(A)
        j = 0
        # determin negative and positive part
        while (j < N) and (A[j] < 0):
            j+=1
        i = j-1
        ans = []
        while (i>=0 and j < N):
            if(A[i]**2 < A[j]**2):
                ans.append(A[i]**2)
                i -= 1
            else:
                ans.append(A[j]**2)
                j += 1
        
        while i >= 0:
            ans.append(A[i]**2)
            i -= 1
            
        while j<N:
            ans.append(A[j]**2)
            j += 1
        return ans