977 - Squares Of A Sorted Array

#easy
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104

1,2,3,4,5,.: 递增排列  

9,8,7,6,5.: 递减排列  

1,2,3,3,4,5,8,8,.: 非递减排列  non-decreasing

9,8,7,7,6,5,5,2,1,.: 非递增排列 non-ascending

使用雙指針法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result(nums.size(), 0);
        int it = nums.size() - 1;
        for ( int leftIndex = 0, rightIndex = nums.size() - 1; leftIndex <= rightIndex;  ) {
            if ( nums[leftIndex]*nums[leftIndex] > nums[rightIndex]*nums[rightIndex] ) {
                result[it] = nums[leftIndex]*nums[leftIndex];
                it--;
                leftIndex++;
            }
            else {
                result[it] = nums[rightIndex]*nums[rightIndex];
                it--;
                rightIndex--;
            }

        } // for
        return result;
    }
};

2

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

            it--;
        }

        return result;
    }
};