代码随想录第一章数组977.有序数组的平方

代码随想录 第一章 数组 977.有序数组的平方 题目：977.有序数组的平方 题目描述：给你一个按 非递减顺序 排序的整数数组 nums​，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。 一、思想

在有序数组的平方排序问题中，双指针算法的核心思想是双指针法通过逆向填充最大值的方式，利用原数组的非递减特性，高效构造有序结果：

双指针定位极值 使用两个指针分别指向数组的左端（最小负数）和右端（最大正数） ，通过比较两者的平方值确定当前最大值。逆向填充有序结果 从结果数组的末尾开始填充（k = n-1​），每次将当前最大的平方值逆序插入，确保结果数组自然升序。 二、代码 /** * 该函数用于计算给定整数数组的平方后排序后的结果 * @param nums 输入的整数数组 * @return 平方后排序后的结果 */ class Solution { public: vector<int> sortedSquares(vector<int> &nums) { // 初始化结果数组的索引 int k = nums.size() - 1; // 创建结果数组 vector<int> res(nums.size()); // 双指针法，从数组两端开始比较，将较大的平方值放入结果数组 for (int left = 0, right = nums.size() - 1; left <= right;) { // 如果左边元素的平方大于右边元素的平方 if (nums[left] * nums[left] > nums[right] * nums[right]) { // 将左边元素的平方放入结果数组 res[k--] = nums[left] * nums[left]; // 左指针右移 left++; } else { // 将右边元素的平方放入结果数组 res[k--] = nums[right] * nums[right]; // 右指针左移 right--; } } // 返回结果数组 return res; } }; 三、解析 1. 算法工作原理分解

步骤 1：初始化指针 创建两个指针 left​（指向数组左端，初始为 0）和 right​（指向数组右端，初始为 n-1​），以及结果数组 res​ 的填充索引 k = n-1​。

步骤 2：循环比较与填充 每次循环比较 nums[left]​ 和 nums[right]​ 的平方值：

若 nums[left]^2 > nums[right]^2​，将 nums[left]^2​ 放入 res[k]​，然后 left​​ 右移（left++​）。否则，将 nums[right]^2​ 放入 res[k]​，然后 right​ 左移（right--​）。无论哪种情况，k​ 递减（k--​）。

步骤 3：终止条件 当 left > right​ 时，所有元素已处理完毕，返回 res​。

2. 关键点说明 关键点说明双指针方向左指针从数组最小负数端出发，右指针从最大正数端出发，向中间移动。逆序填充的必要性平方后的最大值只能从两端产生，逆序填充（从后往前）保证结果直接有序。循环条件 ​left <= right​​必须包含 left == right​ 的情况，否则最后一个元素会被遗漏。 四、复杂度分析 时间复杂度：O(n) 双指针 left​ 和 right​ 从两端向中间移动，每个元素仅被访问一次，总循环次数为 n​（数组长度），每一步操作（平方计算、比较、赋值）均为常数时间。快指针需要遍历整个数组一次，最坏情况下需要检查数组中的每个元素（n 为数组长度）。空间复杂度：O(n) 需要额外创建一个长度为 n​ 的结果数组 res​ 存储平方后的有序值。

‍