LeetCode 977.有序数组的平方

题目描述：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：
最容易想到的方法就是先平方再排序，这样时间复杂度O(nlogn)

但是这题有A的非递减特性可以利用，非负数的平方还是一个非递减顺序，负数的平方是一个非递增序列，将其逆序就是非递减序列了。于是可以先找到非负数和负数的分界线，然后使用双指针依次比较非负数和负数平方后的数值，填入较小的数值，指针后移。
然后注意双指针的边界条件即可。
时间复杂度是O(n)，我使用一个临时数组存储了序列平方后的数值，空间复杂度O(n)。因为个人觉得如果每次都将数平方比较的话，乘法运算耗时较长，所以使用了临时数组。

代码：

class Solution {
private:
    vector<int> ans;
public:
    
    /**
     给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
     **/
    vector<int> sortedSquares(vector<int>& A) {
        
        // 找到数组中非负数和负数的分界位置
        int i = 0; // i指向非负数的第一个位置
        while (i <= A.size()-1) {
            if (A[i] < 0) {
                ++i;
            }else break;
        }
        int size = (int)A.size();
        if (i == A.size()) {// 没有非负数，即全是负数，则其平方逆序即可
            ans.resize(A.size());
            
            for (int i = 0; i < A.size(); ++i) {
                ans[size-1-i] = A[i]*A[i];
            }
        }else{
            // 存在非负数，需要对平方后的逆序和正序序列归并排序
            vector<int> tmp;
            tmp.resize(size);
            for (int k = 0; k < A.size(); ++k) {
                tmp[k] = A[k]*A[k];
            }
            int left = i-1, right = i;
            while (left >= 0 && right < size) {
                if (tmp[left] <= tmp[right]) {
                    ans.push_back(tmp[left]);
                    --left;
                }else{
                    ans.push_back(tmp[right]);
                    ++right;
                }
            }
            
            while (left >= 0) {
                ans.push_back(tmp[left]);
                --left;
            }
            
            while (right < size) {
                ans.push_back(tmp[right]);
                ++right;
            }
        }
        return ans;
    }
};