給定一個按非遞減順序排序的整數(shù)數(shù)組 A，返回每個數(shù)字的平方組成的新數(shù)組，要求也按非遞減順序排序。

示例 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 已按非遞減順序排序。

一開始也是沒有什么思路，連排序都沒想到，后來參考了一下專家的解法，豁然開朗

方法一：排序
思路與算法

創(chuàng)建一個新的數(shù)組，它每個元素是給定數(shù)組對應(yīng)位置元素的平方，然后排序這個數(shù)組。這對于Python比較方便，它有自帶的sort方法

方法二：雙指針
思路
因為數(shù)組 A 已經(jīng)排好序了， 所以可以說數(shù)組中的負(fù)數(shù)已經(jīng)按照平方值降序排好了，數(shù)組中的非負(fù)數(shù)已經(jīng)按照平方值升序排好了。

算法

首先，確定正值和負(fù)值臨界點，然后正值部分向尾部走，負(fù)值部分向頭部走。接下來就是比較數(shù)字平方的大小，依次放入一個空列表

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