977. Squares of a Sorted Array

https://leetcode.com/problems/squares-of-a-sorted-array/

给定整数数组的按平方值排序。暴力法O(NlgN)，进一步优化=>O(N)。负数范围是一个排好序的序列，正数同样，每步都是按序从它们中各自最小或最大的选一个，因此用两个指针指向数组两边，每次选大的倒着插入到res。

/*
 * @lc app=leetcode id=977 lang=cpp
 *
 * [977] Squares of a Sorted Array
 */

// @lc code=start
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        const int N = A.size();
        vector<int> res(N, 0);
        for (int i = 0, j = N - 1, k = N - 1; k >= 0; --k) {
            if (abs(A[i]) < abs(A[j])) res[k] = A[j] * A[j--]; 
            else res[k] = A[i] * A[i++]; 
        } 
        return res;
    }
};
// @lc code=end