977.有序数组的平方

题目

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

思路

数组有序， 负数平方之后会有可能成为最大数。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

• 定义一个新数组res，和A数组一样的大小，让k指向result数组终止位置。
• 如果A[i] * A[i] < A[j] * A[j] 那么res[k--] = A[j] * A[j]; 。
• 如果A[i] * A[i] >= A[j] * A[j] 那么res[k--] = A[i] * A[i]; 。

代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int left = 0, right = A.size()-1;
        vector<int> res(A.size(),0);
        int k = A.size()-1;
        for(int i=left,j=right;i<=j;){
            if(A[i]*A[i]<=A[j]*A[j]){
                res[k--] = A[j]*A[j];
                j--;
            }else{
                res[k--] = A[i]*A[i];
                i++;
            }
        }
        return res;
    }
};