题目

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

解答

方法1

可以简单粗暴的全部平方后，然后再重排序。

方法2

很容易注意到，负数平方后就是个正数了，如果可以从正数负数的分界线开始，向两侧同时遍历，找出较小的那个放入结果数组中，就可以在一遍循环中解决问题了。

因此，我们就可以使用双指针的方法。

具体操作步骤如下：
1.找到数组中间正数负数的分界点，用一个指针指向负数，另一个指针指向正数。
2.比较两个指针所指数值的平方大小，将较小的那个放入结果数组，并将指针的index正确的增大或者减小1。
3.反复如此，直到两个指针均到达数组边界。

代码实现

public int[] sortedSquares(int[] A) {

    int i = 0;
    while (i < A.length && A[i] < 0) {
        i++; // i 表示从中间开的第一个非负数
    }

    int j = i - 1; // j 表示从中间开始的第一个负数

    int[] ans = new int[A.length];

    // 循环数组元素个数那么多次
    for (int x = 0; x < A.length; x++) {
        if (i < A.length && j >= 0) {
            // 如果两个游标都在范围内，就进行比较
            if (A[i] * A[i] > A[j] * A[j]) {
                ans[x] = A[j] * A[j];
                j--;
            } else {
                ans[x] = A[i] * A[i];
                i++;
            }
        } else if (i < A.length) {
            // 否则的话就直接赋值
            ans[x] = A[i] * A[i];
            i++;
        } else if (j >= 0) {
            ans[x] = A[j] * A[j];
            j--;
        }
    }

    return ans;
}