简单

给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题

思路：

使用双指针的方式，从两头往中间走，比对比的结果放到另一个结果表里。

 static int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int k = right;
        while (left <= right) {//left大于right，两个指标已经相遇过了
            int lsum = nums[left] * nums[left];
            lsum = lsum < 0 ? -lsum : lsum;
            int rsum = nums[right] * nums[right];
            rsum = rsum < 0 ? -rsum : rsum;
            if (rsum > lsum) {
                result[k--] = rsum;
                right--;
            } else {
                result[k--] = lsum;
                left++;
            }
        }

        return result;
    }