力扣977. 有序数组的平方

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

方法：双指针，分别指向数组的首尾 

class Solution {
public:
    /*以下方法简单，但是不推荐，时间复杂度是 O(n + nlogn)*/
    // vector<int> sortedSquares(vector<int>& nums) {
    //     for(int i = 0; i < nums.size(); ++i) {
    //         nums[i] *= nums[i];
    //     }
    //     sort(nums.begin(),nums.end()); 快速排序
    //     return nums;
    // }

    /*双指针法，由于数组是递增顺序排列的，平方后最大的数一定不是在最左边就是在最右边，不可能在中间
    所以我们从两边进行平方比较*/
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result(nums.size(), 0);
        int k = nums.size() - 1;
        //i指向数组的开始位置，j指向数组的终止位置
        for(int i = 0, j = nums.size() - 1; i <= j;) { //i <= j，是为了考虑i和j中间有一个元素的情况
            if(nums[i] * nums[i] < nums[j] * nums[j]) {
                result[k--] = nums[j] * nums[j];
                --j;
            }
            else{
                result[k--] = nums[i] * nums[i];
                ++i;
            }
        }
        return result;
    }
    //时间复杂度：O(n)
};