本文为 977.有序数组的平方 的解法，部分图文参考自代码随想录977.有序数组的平方。

1.题目1：977. 有序数组的平方

1.1.解法1：直接排序

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

● 时间复杂度：\(O(nlogn)\)
● 空间复杂度：\(O(logn)\)

1.2.解法2：双指针法

1.题目分析
题目所给定的数组为非递减顺序排序的整数数组，例如：[-4, -1, 0, 3, 10]。
该数组各元素平方后为：[16, 1, 0, 9, 100]，原数组能够划分为两部分：负数 - 0和正数，左侧平方后单调递减，右侧平方后仍单调递增。
2.双指针
定义一个新数组ans，和nums数组一样的大小，让k指向ans数组终止位置。
设置双指针i、j分别指向数组首和尾，皆向内依次进行对比：
nums[i] * nums[i] < nums[j] * nums[j]，ans[k] = nums[j] * nums[j]，j--；
nums[i] * nums[i] >= nums[j] * nums[j]，ans[k] = nums[i] * nums[i]，i++；
ans[k]取两个指针所指向的元素中 更大的元素，随后移动到前一个位置（k--），再次进行以上对比。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int>ans(n, 0);
        int i = 0, j = n - 1, k = n - 1;
        while (i <= j) { // 注意这里要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;
    }
};

● 时间复杂度：\(O(n)\)
● 空间复杂度：\(O(1)\)