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 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

思路

刚看到这一题的时候，脑子里首先想到的就是直接每个数平方一下在排下序就搞定了，但是进阶里面也说明了，如果要对每一个元素进行平方再进行排序，效率会很低，要寻找一种 O(n) 的解决方案。所以还是直接放弃这种方案吧。

双指针

如果从先平方再排序的思路来进行优化的话，影响排序是因为有负数的存在，如果有0的话那么0一定是平方最小，而如果没有0的话，而从左到右的最后一个负数或者第一个正数，一定是整个数组里面平方最小的数。那么可以借助归并排序的思路。从这个负数与非负数的边界位置向两边分开进行查找，再依次比较即可。

public int[] sortedSquares(int[] nums) {
    if (nums == null || nums.length == 0) {
        return nums;
    }
    int i = 0;
    // 获取第一个非负数的位置
    for (; i < nums.length; i++) {
        if (nums[i] >= 0) {
            break;
        }
    }
    // 最后一个负数的位置
    int left = i - 1;
    // 第一个非负数的位置
    int right = i;
    // merge结果数组
    int[] tmp = new int[nums.length];
    int index = 0;
    while (left >= 0 && right < nums.length) {
        if (nums[left] * nums[left] < nums[right] * nums[right]) {
            tmp[index++] = nums[left] * nums[left];
            left--;
        } else {
            tmp[index++] = nums[right] * nums[right];
            right++;
        }
    }
    while (left >= 0) {
        tmp[index++] = nums[left] * nums[left];
        left--;
    }
    while (right < nums.length) {
        tmp[index++] = nums[right] * nums[right];
        right++;
    }
    return tmp;
}

双指针优化

上面的方案需要从中间开始找，要先找到负数与非负数的边界，再从该边界向两边寻找。需要注意两边不能越界，而边界问题一直是编码中很烦人的问题。试用下反向思维，从中间开始找是从最小的开始，那我也可以从最大的开始，使用双指针从两边向中间找，两个指针相遇就停止，相对于上面的方法节省了很多代码量。

public int[] sortedSquares(int[] nums) {
    if (nums == null || nums.length == 0) {
        return nums;
    }
    int[] tmp = new int[nums.length];
    int left = 0;
    int right = nums.length - 1;
    int index = nums.length - 1;
    while(left <= right){
        if(nums[left] * nums[left] >= nums[right] * nums[right]){
            tmp[index--] = nums[left] * nums[left];
            left++;
        }else{
            tmp[index--] = nums[right] * nums[right];
            right--;
        }
    }
    return tmp;
}