[977] 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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]

提示：

nums 已按 非递减顺序 排序

进阶：

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

这道题不知道为何被官方分到动态规划类型了……明明是一个双指针问题。

这道题如果允许排序的话会非常简单，直接排序后map求平方即可。

但是题目要求的时间复杂度为O(n)，因此我们需要借助双指针来在一次遍历之内求解。

如果按照题目要求，从小到大入队，我们首先必须找到平方后最小的那个数所在的位置。

然后以此位置为起点，双指针向两侧遍历并比对平方值大小，将小的那个入队，之后响应指针移动至下一个节点。

当左右指针有一方到达边界时，若左指针未到边界，则按照逆序，平方入队；若右指针未到边界，则按照顺序，平方入队。

function sortedSquares(nums: number[]): number[] {
  const last = nums.length - 1;
  const res: number[] = [];

  // right指针找出最小的非负整数的位置
  let right = last;
  for (let i = last; i >= 0; i--) {
    if (nums[i] < 0) break;
    right = i;
  }

  let left = right - 1;

  while (left >= 0 && right <= last) {
    const resLeft = Math.pow(nums[left], 2);
    const resRight = Math.pow(nums[right], 2);
    if (resLeft > resRight) {
      res.push(resRight);
      right += 1;
    } else {
      res.push(resLeft);
      left -= 1;
    }
  }

  // 下面最多只会二选一
  for (let i = left; i >= 0; i--) {
    res.push(Math.pow(nums[i], 2));
  }
  for (let i = right; i <= last; i++) {
    res.push(Math.pow(nums[i], 2));
  }

  return res;
}

当然如果题目允许我们不使用队列存储返回值的话，我们可以用逆序存储的方式存入值。（当然顺序存入后在翻转也一样）

这样的好处在于，我们可以省略找平方后最小的那个数所在的位置这一步，双指针直接从左右两侧开始遍历，取较大的值存入即可。

function sortedSquares(nums: number[]): number[] {
  const res: number[] = [];

  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const resLeft = Math.pow(nums[left], 2);
    const resRight = Math.pow(nums[right], 2);
    if (resLeft > resRight) {
      res.unshift(resLeft);
      left += 1;
    } else {
      res.unshift(resRight);
      right -= 1;
    }
  }

  return res;
}