977.有序数组的平方（解法二：双指针算法）

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]
分析：
题目给出数组是有序的，只不过最左边元素如果是负数，负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针算法。
1、定义left指向起始位置，right指向终止位置。
2、定义一个新数组result，和A数组一样的大小，让index指向result数组最后一个元素位置。
如果A[left] * A[left] < A[right] * A[right] 那么result[index–] = A[right] * A[right]; 。
如果A[left] * A[left] >= A[right] * A[right] 那么result[index–] = A[left] * A[left]; 。
如动画所示：

package com.codernav.demo.leetcode.array.removeelement;

import java.util.Arrays;

/**
 * 977. 有序数组的平方
 * 给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
 * 原文地址：https://www.codernav.com/2907.html
 * 更多算法详解：https://www.codernav.com
 */
public class Q_977_1 {
    public static void main(String[] args) {
        int[] result = f(new int[]{-4, -1, 0, 3, 10});
        // 0,1,9,16,100
        System.out.println(Arrays.toString(result));
    }

    private static int[] f(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] result = new int[nums.length];
        int index = result.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                result[index--] = nums[left] * nums[left];
                ++left;
            } else {
                result[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return result;
    }
}

以下写法也是可以的：

package com.codernav.demo.leetcode.array.removeelement;

import java.util.Arrays;

/**
 * 977. 有序数组的平方
 * 给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
 * 原文地址：https://www.codernav.com/2907.html
 * 更多算法详解：https://www.codernav.com
 */
public class Q_977_1 {
    public static void main(String[] args) {
        int[] result = f(new int[]{-4, -1, 0, 3, 10});
        // 0,1,9,16,100
        System.out.println(Arrays.toString(result));
    }

    private static int[] f(int[] nums) {
        // 定义左指针
        int left = 0;
        // 定义右指针
        int right = nums.length - 1;
        // 定义一个新数组，用来存放元素平方值
        int[] result = new int[nums.length];
        // 定义一个下标，指向新数组最后一个元素位置
        int index = result.length - 1;
        while (left <= right) {
            // 最左边元素平方比最右边元素平方大，取最左边元素平方值
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                result[index] = nums[left] * nums[left];
                index--;
                // 取了left，下次就不取这个值了，所以left++
                left++;
            } else { // 最右边元素平方比最左边元素平方大，取最右边元素平方值
                result[index] = nums[right] * nums[right];
                index--;
                // 取了right，下次就不取这个值了，所以right++
                right--;
            }
        }

        return result;

    }
}