###### tags: `Leetcode` `easy` `pointer` `array` `sort` `python` `c++`

# 977. Squares of a Sorted Array

## [題目連結:] https://leetcode.com/problems/squares-of-a-sorted-array/description/

## 題目:
Given an integer array ```nums``` sorted in **non-decreasing** order, return an array of **the squares of each number** sorted in non-decreasing order.

**Follow up**: Squaring each element and sorting the new array is very trivial, could you find an ```O(n)``` solution using a different approach?

**Example 1:**

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

**Example 2:**

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

## 解題想法:
* 題目為給一 non-decreasing非遞減之數列(由小到大，可以有重複)
* 求裡面元素平方之後，由小到大排序
* 要求time: O(n)

* 因為給non-decreasing，可以利用pointer:
* 每次比較頭尾平方大小
* 逐一選大者記錄在最終答案

## Python:

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        #non-decreasing非遞減
        #use pointer
        #O(n)
        head=0
        tail=len(nums)-1
        res=[0]*len(nums) #紀錄答案
        curPos=len(nums)-1
        while head<=tail:
            SquareHead=nums[head]**2
            SquareTail=nums[tail]**2
            if SquareHead<SquareTail:
                res[curPos]=SquareTail
                tail-=1
            else:
                res[curPos]=SquareHead
                head+=1
            curPos-=1
        return res

## C++:
* 可以直接用絕對值比較大小，因為絕對值越大，平方自然也大

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n=nums.size();
        vector<int> res(n,0);
        int head=0, tail=n-1, curPos=n-1;
        while (head<=tail){
            if (abs(nums[head])<abs(nums[tail])){
                res[curPos]=nums[tail]*nums[tail];
                tail-=1;
            }
            else{
                res[curPos]=nums[head]*nums[head];
                head+=1;
            }
            curPos-=1;
        }
        return res;
    }
};