977. Squares of a Sorted Array

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

/*
    t: O(n), s: O(n)
*/
class Solution {
    public int[] sortedSquares(int[] A) {
        int len = A.length;
        int left = 0;
        int right = len - 1;
        int[] result = new int[len]; //must create a new array to save, or it'll be wrong
        
        for(int i = len - 1; i >= 0; i--) {
            int leftVal = A[left]*A[left];
            int rightVal = A[right]*A[right];
            
            if (leftVal > rightVal) {
                A[i] = leftVal;
                left++;
            } else {
                A[i] = rightVal;
                right--;
            }
        }
        return A;
    }
}

注意...如果不用一個新 array 存, 會錯, 不能 in-place