题目：

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

Java代码：

class Solution { public int[] sortedSquares(int[] A) { int len=A.length; int j=0; while(j<len&&A[j]<0) { j++; } int i=j-1; int t=0; int[] ans=new int[len]; while (j<len&&i>=0){ if(A[j]*A[j]<A[i]*A[i]){ ans[t++]=A[j]*A[j]; j++; }else{ ans[t++]=A[i]*A[i]; i--; } } while(i>=0){ ans[t++]=A[i]*A[i]; i--; } while(j<len){ ans[t++]=A[j]*A[j]; j++; } return ans; } }

思路：

双指针法，因为数组已经排好序，找到最小的负数和非负数，这两个数应该是相邻的，我们可以使用两个指针分别读取数组的非负部分与负数部分 —— 指针 i 反向读取负数部分，指针 j 正向读取非负数部分。

复杂度分析：

时间复杂度：$O(N)$，其中 NN 是数组 A 的长度。 空间复杂度：$O(N)$。