// @Title: 有序数组的平方 (Squares of a Sorted Array)
// @Author: qisiii
// @Date: 2022-02-27 09:58:59
// @Runtime: 4 ms
// @Memory: 43 MB
// @comment: 
// @flag: 
class Solution {
    public int[] sortedSquares(int[] nums) {
        if(nums.length<=0){
            return nums;
        }
        for(int i=0;i<nums.length;i++){
            nums[i]=nums[i]*nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

// @Title: 有序数组的平方 (Squares of a Sorted Array)
// @Author: qisiii
// @Date: 2022-03-10 13:05:16
// @Runtime: 1 ms
// @Memory: 42.8 MB
// @comment: 双指针
// @flag: BLUE
class Solution {
    public int[] sortedSquares(int[] nums) {
        if(nums.length<=0){
            return nums;
        }
        int[] result=new int[nums.length];
        int left=0,right=nums.length-1,index=right;
        while(left<right){
            if(Math.abs(nums[left])<Math.abs(nums[right])){
                result[index--]=nums[right]*nums[right];
                right--;
            }else if(Math.abs(nums[left])>Math.abs(nums[right])){
                result[index--]=nums[left]*nums[left];
                left++;
            }else{
                result[index--]=nums[right]*nums[right];
                result[index--]=nums[left]*nums[left];
                left++;
                right--;
            }
        }
        result[0]=nums[left]*nums[left];
        return result;
    }
}

// @Title: 有序数组的平方 (Squares of a Sorted Array)
// @Author: qisiii
// @Date: 2024-09-11 15:01:10
// @Runtime: 1 ms
// @Memory: 46.4 MB
// @comment: 双指针+额外数组空间
// @flag: GREEN
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] resultArray = new int[n];
        int left = 0, right = n - 1;
        while (left <= right) {
            int leftValue = nums[left] * nums[left];
            int rightValue = nums[right] * nums[right];
            int value = leftValue;
            if (leftValue > rightValue) {
                left++;
            } else {
                value = rightValue;
                right--;
            }
            resultArray[--n] = value;
        }
        return resultArray;
    }
}