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

进阶：

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

双指针-归并排序，找到正负元素的分界线，从前往后，从小到大填充ans。

我们的的第一反应是用 for 循环构造平方后的数组，然后再用 Arrays.sort() 方法对平方后的数组进行排序。能否优化一下呢？

注意到数组 nums 已经按照升序排序，因此平方数组一定有规律。

如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。

因此，对于一个有正有负的数组，它的平方数组中一定存在一个分界线，分界线左边是负数的平方，降序，分界线右边是正数的平方，升序。 所以我们只需要把这两个有序的子数组合并成一个升序的数组即可。

注意到平方数组中的分界线就是原数组中的分界线，所以我们需要先找到原数组中的分界线，然后从分界线开始，向两侧遍历，用双指针法合并两个有序数组。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length; // 获取数组的长度
        int negative = -1; // 记录最后一个负数的索引
        
        // 因为数组是非递减顺序排列的，所以我们要找到最后一个负数的索引，即负数与非负数的分界线，然后一个指针倒序遍历负数，一个指针正序遍历非负数。之所以要倒序遍历负数，是因为负数越大，平方越小。
        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                negative = i; // 更新最后一个负数的索引
            } else {
                break; // 遇到第一个非负数时，停止循环
            }
        }

        int[] ans = new int[n]; // 用于存储结果的数组
        int index = 0; // 结果数组的当前索引
        
        int i = negative; // 从最后一个负数开始
        int j = negative + 1; // 从第一个非负数开始
        
        // 合并排序负数和非负数的平方值，有点类似合并两个升序链表。
        while (i >= 0 || j < n) { 
            if (i < 0) { // 如果所有负数已经处理完
                ans[index] = nums[j] * nums[j]; // 只处理非负数
                ++j;
            } else if (j == n) { // 如果所有非负数已经处理完
                ans[index] = nums[i] * nums[i]; // 只处理负数
                --i;
            } else if (nums[i] * nums[i] < nums[j] * nums[j]) { // 比较负数平方和非负数平方的大小
                ans[index] = nums[i] * nums[i]; // 如果负数的平方较小
                --i; // 移动到下一个负数
            } else {
                ans[index] = nums[j] * nums[j]; // 如果非负数的平方较小
                ++j; // 移动到下一个非负数
            }
            
            ++index; // 更新结果数组的索引
        }

        return ans; // 返回排序后的平方数组
    }
}

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。

左右指针，从大到小填充ans。

注意到平方数组只可能是先减后增或递增的，所以平方数组的最大值一定在两端取得，所以我们可以用左右指针从两端往中间“磨”。

注意不能原地修改数组，因为数组中最后一个数的平方比第一个数的平方小的话，以后还要用最后一个数。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length; // 获取数组的长度
        int[] ans = new int[n]; // 创建一个新的数组用于存储结果
        int i = 0, j = n - 1, pos = n - 1; // 初始化双指针和结果数组的插入位置
        // 注意不能让pos从0到n-1遍历，即从前往后填充ans，因为平方值是从两端向中间缩小的，即一开始i和j指向的数组元素的平方值一定有一个是整个平方数组中的最大值，所以要从后往前填充ans。
        // 从后往前的话，不能原地修改，必须用新数组。

        // 使用双指针法，i 从左向右移动，j 从右向左移动
        while (i <= j) {
            // 比较 nums[i] 和 nums[j] 的平方值
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                // 如果左侧的平方值大于右侧的平方值，将左侧的平方值放入结果数组
                ans[pos] = nums[i] * nums[i];
                ++i; // 移动左指针向右
            } else {
                // 如果右侧的平方值大于或等于左侧的平方值，将右侧的平方值放入结果数组
                ans[pos] = nums[j] * nums[j];
                --j; // 移动右指针向左
            }
            --pos; // 结果数组的位置向前移动
        }
        return ans; // 返回排序后的平方数组
    }
}

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。