1. 题目

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

2. 示例

3. 分析

我们当然可以遍历数组平方元素，然后再使用sort排序，但这里时间复杂度就为 O(logN) 了。

我们可以尝试 O(N) 的时间复杂度解决：

新开辟一个res数组用于存储已排完序的元素。定义两个指针 i、j，分别指向原数组第一位和最后一位。因为当前原数组是升序的，所以我们可以通过选择两个指针对应元素的绝对值中较大的数平方后逆序(从右往左)放进res数组。

注意：不能选择当前两个指针的较小值正序(从左往右)放入res数组，因为此时的较小值可能不为原数组某个元素平方后的最小值。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);

        for(int i = 0, j = n-1, pos = n-1; i <= j;)
        {
            if(abs(nums[i]) > abs(nums[j]))
            {
                res[pos] = nums[i]*nums[i];
                i++;
            }
            else
            {
                res[pos] = nums[j]*nums[j];
                j--;
            }
            pos--;
        }
        return res;
    }
};