93 lines
1.9 KiB
Markdown
93 lines
1.9 KiB
Markdown
## 每日一题 - 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.
|
||
|
||
```
|
||
|
||
### 思路
|
||
|
||
典型的双指针问题。我们记录头尾指针，
|
||
然后每次`移动两个指针指向的值中绝对值较大的那个`就好了。
|
||
|
||
这个很好理解，因为是从小到大排列，我们可以获取到最小的元素和最大的元素。
|
||
平方较大的元素一定是最小的元素或者最大的元素，因此我们两个指针指向首尾就好了。
|
||
|
||
更新的策略也很简单，由于我们取得的绝对值是从大到小的，因此我们新建一个数组，
|
||
然后从后面往前放就好了。
|
||
|
||
### 参考答案
|
||
|
||
```js
|
||
|
||
/*
|
||
* @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;
|
||
};
|
||
|
||
|
||
```
|
||
|
||
### 其他优秀解答
|
||
```
|
||
暂无
|
||
```
|