0977.有序数组的平方
难度：🟢 简单
标签：数组、双指针、排序
链接：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]
解题思路
核心思想
本题的核心挑战在于，原始数组虽然是有序的，但由于负数的存在，平方后的数组大小关系会发生变化。例如，-4 的平方是 16，而 3 的平方是 9。我们可以观察到，平方后最大的值必然产生于原数组的“两端”（绝对值最大的数，要么在最左边，要么在最右边）。
思路选择
双指针法 是解决此问题的最优思路。
我们可以创建两个指针，
left指向数组的头部，right指向数组的尾部。比较
nums[left]和nums[right]的平方值。较大的那个平方值，一定是结果数组中最大的元素。我们可以创建一个与原数组等长的结果数组，并从后向前填充。每次比较后，将较大的平方值放入结果数组的末尾，然后移动相应的指针（
left或right）。
关键步骤
初始化：
left指针指向0。right指针指向nums.length - 1。创建一个与
nums等长的空结果数组result。创建一个写入指针
writeIndex指向result的末尾，即nums.length - 1。
循环条件：当
left <= right时，表示还有未处理的元素，持续循环。比较与填充： a. 比较
nums[left]的平方和nums[right]的平方。 b. 如果左边的平方更大，则将其放入result[writeIndex]，然后left++。 c. 否则，将右边的平方放入result[writeIndex]，然后right--。移动写入指针：每填充一个数后，将
writeIndex减一。返回结果：循环结束后，
result数组就包含了所有元素的平方，并且已经按非递减顺序排好。
代码实现 (推荐)
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
const n = nums.length;
const result = new Array(n);
let left = 0, right = n - 1;
let writeIndex = n - 1;
while (left <= right) {
const leftSquare = nums[left] * nums[left];
const rightSquare = nums[right] * nums[right];
if (leftSquare > rightSquare) {
result[writeIndex] = leftSquare;
left++;
} else {
result[writeIndex] = rightSquare;
right--;
}
writeIndex--;
}
return result;
};
原始代码分析 (用户提供)
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function (nums) {
let left = 0, right = nums.length - 1, results = [];
while (left <= right) {
let leftNum = nums[left] * nums[left];
let rightNum = nums[right] * nums[right];
if (leftNum > rightNum) {
// unshift 操作会将所有已存在的元素向后移动一位，时间复杂度为 O(k)
results.unshift(leftNum);
left++;
} else {
results.unshift(rightNum);
right--;
}
}
return results;
};
复杂度分析
时间复杂度：O(n) 其中 n 是数组
nums的长度。我们只需要对数组进行一次完整的遍历。空间复杂度：O(1) 不考虑存储返回结果的数组，我们只使用了常数个额外变量作为指针，空间消耗是恒定的。
相关题目
总结
本题是双指针思想的绝佳应用。通过利用原数组部分有序的特性（平方后最大值在两端），我们可以从后向前构建结果数组，从而在一次遍历内完成排序，达到 O(n) 的时间复杂度和 O(1) 的额外空间复杂度。