2019-07-18.md

每日一题 - squares-of-a-sorted-array

信息卡片

• 时间：2019-07-18
• 题目链接：https://leetcode.com/problems/squares-of-a-sorted-array/
• tag：Array Two Pointers

题目描述

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

 

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]
 

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

思路

典型的双指针问题。我们记录头尾指针， 然后每次移动两个指针指向的值中绝对值较大的那个就好了。

这个很好理解，因为是从小到大排列，我们可以获取到最小的元素和最大的元素。 平方较大的元素一定是最小的元素或者最大的元素，因此我们两个指针指向首尾就好了。

更新的策略也很简单，由于我们取得的绝对值是从大到小的，因此我们新建一个数组， 然后从后面往前放就好了。

参考答案

/*
 * @lc app=leetcode id=977 lang=javascript
 *
 * [977] Squares of a Sorted Array
 */
/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortedSquares = function(A) {
  let start = 0;
  let end = A.length - 1;
  const res = [];
  let cur = 0;

  while (start <= end) {
    if (Math.abs(A[start]) === Math.abs(A[end])) {
      cur++;
      res[A.length - cur] = A[start] * A[start];
      cur++
      res[A.length - cur] = A[end] * A[end];
      start++;
      end--;
    } else if (Math.abs(A[start]) > Math.abs(A[end])) {
      cur++;
      res[A.length - cur] = A[start] * A[start];
      start++;
    } else {
      cur++;
      res[A.length - cur] = A[end] * A[end];
      end--;
    }
  }

  return res;
};

其他优秀解答

暂无