[LeetCode 977] 有序数组的平方

🎯 请点击上方原题链接，查看题目描述👆

💭 解题思路#

由于原数组是递增的，并且里面存在负数，所以平方后的结果是向中间收敛的（存在负数的情况）

开辟一个新的数组空间，使用两个指针，一个在开头处、一个在结尾处
分别平方两个指针所指元素，大的就存到新数组里面

💻 代码实现#

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int left = 0,right = n - 1;

        int[] res = new int[n];
        //升序排序，所以从右边开始插入
        int index = n - 1;
        while(left <= right){
            int leftSquares = nums[left] * nums[left];
            int rightSquares = nums[right] * nums[right];
            if(leftSquares >= rightSquares){
                res[index] = leftSquares;
                left++;
            }else{
                res[index] = rightSquares;
                right--;
            }
            index--;
        }
        return res;
    }
}