第335题(2020-10-27)：leetcode977： 有序数组的平方？

[qappleh]

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

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

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

  提示：

• 1 <= A.length <= 10000
• -10000 <= A[i] <= 10000
• A 已按非递减顺序排序。

[qappleh]

1.双指针解法

原数组是非递减排列的，元素的平方和最大，要么是第一项，要么是最后一项。

维护头尾指针，所指向的元素，平方和更大者，安排到结果数组的最后一项。

指针相应的更新，继续比较头尾元素的平方和，较大者，安排到结果数组的倒数第二项。

以此类推。把结束数组的所有元素填满。

代码 时间复杂度：O(n)O(n)，空间复杂度：O(n)O(n)

const sortedSquares = (A) => {
  let start = 0;
  let end = A.length - 1;
  const res = new Array(A.length);

  for (let i = A.length - 1; i >= 0; i--) {
    const s = A[start] * A[start];
    const e = A[end] * A[end];
    if (s > e) {
      res[i] = s;
      start++;
    } else {
      res[i] = e;
      end--;
    }
  }

  return res;
};

2.用库函数 (偶尔偷偷懒)

const sortedSquares = (A) => {
  return A.map(e => e * e).sort((a, b) => a - b);
};