力扣977.有序数组的平方（双指针）

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

方法一：直接将每个元素的平方压入ans数组中，再对ans数组进行排序

class Solution 
{
public:
    vector<int> sortedSquares(vector<int>& nums) 
    {
        vector<int>ans;
        for(int x:nums)
        {
            ans.emplace_back(x*x);
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};

方法二：双指针

题目给我们的数组是一个非递减的数组，那么我们可以利用好这个条件减小时间复杂度。

操作方法如下：由于是非递减数组，并且其中可能有负数，那么平方后最大的两个数只有可能是第一个（即负数中最小的那个）和最后一个（即正数中最大的那个）。我们可以想到双指针，一个从前往后，一个从后往前，分别比较指向元素平方后的大小。然后给一个位置指针k，标记要存入的位置。比较后我们将较大的元素存到k这个位置，然后k自减，指向平方后较大的元素的指针就移动一位，重复上述过程

class Solution 
{
public:
    vector<int> sortedSquares(vector<int>& nums) 
    {
        vector<int>ans(nums.size(),0);
        int k=nums.size()-1;
        int i=0,j=k;
        while(i<=j)//要取等，否则若有奇数个元素，中间那个会没有处理
        {
            if(nums[i]*nums[i]<nums[j]*nums[j])
            {
                ans[k--]=nums[j]*nums[j];
                j--;
            }
            else
            {
                ans[k--]=nums[i]*nums[i];
                i++;
            }
        }
        return ans;
    }
};