#有序数组的平方

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按非递减顺序排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

#解题思路

题目信息：非递减顺序，O(n)

#思路一

首先，考虑暴力解法，循环遍历 nums 逐个进行平方处理，处理后再按非递减顺序排序，复杂度 O(由排序算法决定)

#思路二

其次可以想到双指针法，由于是非递减顺序，右指针指向尾部，左指针指向头部，两个指针同时向中间遍历，将元素平方后比较，大的那个放入新数组，最后翻转数组，复杂度 O(n)

#首次代码

function sortedSquares(nums: number[]): number[] {
  let left = 0
  let right = nums.length - 1
  let result = []

  while (left <= right) {
    const leftVal = nums[left] * nums[left]
    const rightVal = nums[right] * nums[right]

    if (rightVal > leftVal) {
      result.push(rightVal)
      right--
    } else {
      result.push(leftVal)
      left++
    }
  }

  return result.reverse()
}

#代码优化

可以通过下标放入结果，不需要翻转数组

function sortedSquares(nums: number[]): number[] {
  let left = 0
  let right = nums.length - 1
  let index = nums.length - 1
  let result = []

  while (left <= right) {
    const leftVal = nums[left] * nums[left]
    const rightVal = nums[right] * nums[right]

    if (rightVal > leftVal) {
      result[index--] = rightVal
      right--
    } else {
      result[index--] = leftVal
      left++
    }
  }

  return result
}