来看leetcode上的一道经典题目，leetcode.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]

提示：

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

 

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题最基本的思路是先对每个数进行平方，然后再进行排序，时间复杂度是O(n + nlog n) 代码如下：

 	let res = [];
    for (let num of nums) {
      res.push(num * num);
    }
    res.sort((a, b) => a - b);

基本思路比较简单，每个人都能看懂，但是在面试的时候往往追求的是高大上，要体现自己的能力所在，因此需要对高级思路有个了解，才能在面试在取得比较好的表现。

题目的进阶要求是设计O(n)的算法来解决问题，仔细查看题目所给数据，我们可以观察到这样的特点：当将数组中每个数都平方之后，最大的数要么在最左边要么在最右边(负数平方之后可能比右边的正数大)，这个规律是可以依次递推的，因此可以利用这个规律将数组最左边和最右边依次对比取最大，然后取完最大之后将这个最大插入结果数组，再继续遍历。

代码如下：

  let n = nums.length;
  let res = new Array(n).fill(0);	// res声明并初始化
  let i = 0,
    j = n - 1,
    k = n - 1;
  while (i <= j) {
    // 计算左边和右边的平方
    let left = nums[i] * nums[i],
      right = nums[j] * nums[j];
    if (left < right) {
      // 右边是最大的情况
      res[k--] = right;
      j--;
    } else {
      // 左边是最大的情况
      res[k--] = left;
      i++;
    }
  }
  return res;

上述代码参考代码随想录中提供的js版本：https://www.programmercarl.com/0977.有序数组的平方.html