leetcode977 有序数组的平方

双指针+归并排序
时间复杂度:O(n)
空间复杂度:O(1) 除了存储答案的数组以外，我们只需要维护常量空间。

var sortedSquares = function(nums) {
let middle = -1
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] < 0) {
      // 寻找分界点
      middle = i
    }
  }
  let left = middle
  let right = middle + 1
  let arr = []
  while (left > -1 || right < nums.length) {
    console.log('left', left, right)
    if (left < 0) {
    //   都是正数
      arr.push(nums[right] * nums[right])
      right++
    } else if (right === nums.length) {
    //   都是负数
      arr.push(nums[left] * nums[left])
      left--
    } else if (nums[left] * nums[left] > nums[right] * nums[right]) {
      // 如果第一个负数 大于 负数所在的下一个 ，就把下一个push进去，因为是从小到大排序的；这种情况只能是 -2，1的情况
      arr.push(nums[right] * nums[right])
      right++
    } else {
      // 如果第一个负数 小于负数所在的下一个，就把负数push进去，这种情况只能是 -1,2的情况
      arr.push(nums[left] * nums[left])
      left--
    }
  }
  return arr
};