977. Squares of a Sorted Array

// Author: Tecker 19/02/28
// Time: O(logN + N)
// Space: O(N)
vector<int> sortedSquares(vector<int>& A) {
    if (A.size()==1) {
        A[0]*=A[0];
        return A;
    }
	// 查找>=0的位置
    int pos = lower_bound(begin(A), end(A), 0) - begin(A);

    vector<int> res(A.size());
	// 回退一位使 i 指向可能存在的负数或头部，j指向正数或 0
    int i= (pos>0) ? pos-1 : 0;
    int j= i+1;
    pos = 0;
	// i 一边向头部，j 向尾部合并成有序数组
    while(i>=0 && j<=A.size()-1) {
        int sub=abs(A[i])-A[j];
        if (sub<0)
            res[pos++] = pow(A[i--], 2);
        else if (sub>0)
            res[pos++] = pow(A[j++], 2);
        else {
            res[pos++] = pow(A[i--], 2);
            res[pos++] = pow(A[j++], 2);
        }
    }

    while (i>=0)
        res[pos++] = pow(A[i--], 2);
    while (j<=A.size()-1)
        res[pos++] = pow(A[j++], 2);

    return res;
}