# 0977. Squares of a Sorted Array
###### tags: `Leetcode` `Easy` `FaceBook`
Link: https://leetcode.com/problems/squares-of-a-sorted-array/
## 思路 $O(N)$ $O(1)$
### 思路一
之前的做法是先找到最小值，然后在最小值附近用双指针遍历
### 思路二 (better)
后来发现可以倒着建出答案arr，有点像[0088. Merge Sorted Array](https://hackmd.io/uNTJQ2RaRAWsjYu7prqQlQ)，写起来会更简单
## Code
### 思路一

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        int smallestIdx = 0;
        for(int i = 0;i < nums.length-1;i++){
            if(Math.abs(nums[i])>Math.abs(nums[i+1])){
                smallestIdx = i+1;
            }
        }
        int idx = 0;
        ans[idx] = nums[smallestIdx]*nums[smallestIdx];
        int l = smallestIdx-1, r = smallestIdx+1;
        while(l>=0 && r<=nums.length-1){
            if(Math.abs(nums[l])<Math.abs(nums[r])){
                ans[++idx] = nums[l]*nums[l];
                l--;
            }
            else{
                ans[++idx] = nums[r]*nums[r];
                r++;
            }
        }
        while(r<=nums.length-1){
            ans[++idx] = nums[r]*nums[r]; 
            r++;
        }
        while(l>=0){
            ans[++idx] = nums[l]*nums[l];
            l--;
        }
        return ans;
    }
}

### 思路二

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        int p1 = 0, p2 = nums.length-1;
        int idx = nums.length-1;
        while(p1 <= p2){
            if(Math.abs(nums[p1]) < Math.abs(nums[p2])){
                ans[idx--] = nums[p2]*nums[p2];
                p2--;
            }
            else{
                ans[idx--] = nums[p1]*nums[p1];
                p1++;
            }
        }
        return ans;
    }
}