977. Squares of a Sorted Array

方法1: two pointers Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10] Output: [0,1,9,16,100] Example 2:

Input: [-7,-3,2,3,11] Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000-10000 <= A[i] <= 10000A is sorted in non-decreasing order.

方法1: two pointers

思路：

找到正负数的交界点，负数向左，正数向右，用merge two sorted array的方法merge出result。

class Solution { public: vector<int> sortedSquares(vector<int>& A) { vector<int> result; int n = A.size(), left = -1, right = 0; while (right < n && A[right] < 0) { right++; left++; } while (left >= 0 && right < n) { if (A[left] * A[left] <= A[right] * A[right]) { result.push_back(A[left] * A[left]); left--; } else { result.push_back(A[right] * A[right]); right++; } } while (left >= 0) { result.push_back(A[left] * A[left]); left--; } while (right < n) { result.push_back(A[right] * A[right]); right++; } return result; } };