Day 07 : Squares of a Sorted Array

题目简述：
一个由小到大排列的整数阵列，写一个函式回传每个元素的平方，并且也是由小到大排列

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

直觉联想暴力解：
把每个数平方後，再把结果sort，而这个方法也适用一开始给的array没有sort过

时间复杂度：Ｏ(nlogn)
空间复杂度：Ｏ(n)

function sortedSquaredArray(array) {
  //建一个和array一样大小的Array并全部填入0
  const sortedSquares = new Array(array.length).fill(0);
  for (let i = 0; i < array.length; i++) {
    const value = array[i];
    //把原本的array元素依序平放後放到创建的sortedSquares
    sortedSquares[i] = value * value;
  }
  return sortedSquares.sort((a, b) => a - b);
}

当然暴力後一定要尝试优化！
想想看如何达到Ｏ(n)的时间？
但这个方法成立的前提是一开始array已经是由小到大排列好的
那我们应该要怎麽做？

以Array = [-7,-5,-3,2,3,8,11]为例
我们都知道，越小的负数平方会变成越大的数，且一开始最小的负数会在最左边，最大的数会在最右边

如此，我们可以拿阵列最右边的元素去和最左边的数，两者以绝对值做比较，谁的平方大谁就摆在最右边
相信经过前两天利用指标的方式解题，心里一定有些想法了！！？

没错，就是给建立一个start pointer 和 end pointer分别指向阵列的头尾

一样我们先宣告一个一样大小且塞满0的阵列：[0,0,0,0,0,0,0]

| -7 | < | 11 | → [0,0,0,0,0,0,121]
| -7 | < | 8 | → [0,0,0,0,0,64,121]
| -7 | > | 3 | → [0,0,0,0,49,64,121]

以此类推...

这个方法就可以在Ｏ(n)的时间内解决，而且我们只需要检查一次，空间复杂度一样要Ｏ(n)来建立结果


var sortedSquares = function(nums) {
  const sortedSquares = new Array(nums.length).fill(0);
  let start = 0;
  let end = nums.length - 1;
  for (let i = nums.length - 1; i >= 0; i--) {
    const smallerVal = nums[start];
    const biggerVal = nums[end];
    if (Math.abs(smallerVal) > Math.abs(biggerVal)) {
      sortedSquares[i] = smallerVal * smallerVal;
      start++;
    } else {
      sortedSquares[i] = biggerVal * biggerVal;
      end--;
    }
  }
  return sortedSquares;
};