这道题（LeetCode 977）是非常经典的双指针入门题，也是考察对有序性利用能力的试金石。

下面我将分步骤带你完成这道题的训练。

第一部分：题目描述

题目名称：有序数组的平方 (Squares of a Sorted Array)

【题目描述】 给定一个按非递减顺序排序的整数数组 $A$，其中包含 $n$ 个整数。 请你创建一个新的数组，其中包含 $A$ 中每个元素的平方，并且新数组也必须按非递减顺序排序。

【输入格式】 第一行包含一个整数 $n$，表示数组元素的个数。 第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示给定的有序数组，相邻整数之间用空格分隔。

【输出格式】 输出一行，包含 $n$ 个整数，表示平方后排序好的数组，相邻整数之间用空格分隔。

【输入样例】

5
-4 -1 0 3 10

【输出样例】

0 1 9 16 100

【数据范围与提示】

• $1 \le n \le 10^4$
• $-10^4 \le A_i \le 10^4$
• 数组 $A$ 已按非递减顺序排序。
• 进阶挑战：请设计一个时间复杂度为 $O(n)$ 的算法解决此问题。

第二部分：预备知识点

在解决这道题之前，你需要掌握以下知识：

1. 数组（Array）的基本操作：遍历、索引访问。
2. 排序算法（Sorting）：了解快速排序（std::sort）的时间复杂度是 $O(n \log n)$。
3. 双指针技巧（Two Pointers）：能够在一个序列中同时操作首尾两个指针。
4. 数学性质：$y = x^2$ 的函数图像性质（绝对值越大的数，平方越大）。

第三部分：启发式教学与思路推演

来，拿出草稿纸，我们不要急着写代码，先画图理解。

1. 暴力法的瓶颈

学生：教练，这题很简单啊，我先把所有数平方，然后调用 sort 函数排序不就行了吗？ 教练：没错，这是最直观的解法。

• 草稿纸推演： [-4, -1, 0, 3, 10] $\xrightarrow{平方}$ [16, 1, 0, 9, 100] $\xrightarrow{排序}$ [0, 1, 9, 16, 100]
• 复杂度分析： 平方的过程是 $O(n)$，但排序（通常是快排）的平均复杂度是 $O(n \log n)$。 提问：如果 $n$ 很大（比如 $10^7$），$O(n \log n)$ 可能会超时。题目中原来的数组已经是有序的，暴力法打乱了顺序又重排，是不是浪费了原数组“有序”这个宝贵的条件？

2. 观察数据的“形状”

教练：让我们画一下 $y=x^2$ 的性质。原数组分为负数部分和非负数部分。

• 对于正数：$1, 3, 5 \dots$ 平方后是递增的。
• 对于负数：$-5, -3, -1 \dots$ 平方后是递减的（或者说，绝对值是递减的）。

图示引导： 想象数组元素分布在一个数轴上，平方操作就像把数轴的两端“向上折叠”成一个 U 型。

原数组：     -4   -1   0    3      10
              |    |   |    |       |
平方后大小： 16    1   0    9      100
              ^                 ^
            (左边)            (右边)

关键发现：数组中平方后最大的元素，一定是在数组的最左端或者最右端！ 不可能出现在中间。

3. 双指针策略（草稿纸模拟）

教练：既然最大的数只可能在两头出现，那我们就每次只比较两头，把最大的那个挑出来，放到结果数组的最后面（逆序填充）。

演示过程： 输入：A = [-4, -1, 0, 3, 10] 准备一个结果数组 res，长度为 5。 指针 L 指向开头 (index 0)，指针 R 指向结尾 (index 4)。k 指向结果数组的末尾 (index 4)。

• 第 1 步：

  • L 指向 -4 (平方是 16)
  • R 指向 10 (平方是 100)
  • 比较：$16 < 100$。
  • 操作：把 100 放入 res[k]。R 向左移，k 向前移。
  • 当前状态：L 在 0 (-4)，R 在 3 (3)，res = [?, ?, ?, ?, 100]

• 第 2 步：

  • L 指向 -4 (平方是 16)
  • R 指向 3 (平方是 9)
  • 比较：$16 > 9$。
  • 操作：把 16 放入 res[k]。L 向右移，k 向前移。
  • 当前状态：L 在 1 (-1)，R 在 3 (3)，res = [?, ?, ?, 16, 100]

• 第 3 步：

  • L 指向 -1 (平方是 1)
  • R 指向 3 (平方是 9)
  • 比较：$1 < 9$。
  • 操作：把 9 放入 res[k]。R 向左移。
  • 当前状态：res = [?, ?, 9, 16, 100]

学生：啊！我明白了！就像两支军队在两头比武，谁赢了谁就去领奖台的最高位置，输的人留下来下一轮继续比。

4. 复杂度与优化

• 时间复杂度：每个元素只被访问一次，指针只移动 $n$ 次，所以是 $O(n)$。这比 $O(n \log n)$ 快得多。
• 空间复杂度：需要一个额外的数组来存结果，$O(n)$。

第四部分：读题关键词

在做此类题目时，圈出以下关键词能帮你快速定位算法：

1. “有序”、“非递减顺序”：这通常暗示可以使用二分查找或双指针。如果题目没用上这个条件，通常你的解法不是最优的。
2. “平方”：暗示负数会变正，破坏原有的单调性，但在绝对值意义上呈现“两头大、中间小”的特征。
3. “时间复杂度 O(n)”：明确禁止使用基于比较的排序（如快排），强制要求线性扫描。

第五部分：NOI 风格参考代码 (C++14)

/**
 * NOI/CSP 风格参考代码
 * 语言标准：C++14
 * 题目：有序数组的平方
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */

#include <iostream>
#include <vector>
#include <algorithm> // 尽管不用sort，但常用头文件建议包含

using namespace std;

// 核心逻辑函数，符合模块化编程习惯
vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n); // 预分配空间，避免频繁 push_back 造成扩容开销
    
    int left = 0;           // 左指针
    int right = n - 1;      // 右指针
    int pos = n - 1;        // 结果数组的填充位置，从后往前填
    
    while (left <= right) {
        // 计算左右两端元素的平方
        // 注意：在实际工程或极大数据时要考虑 overflow，
        // 但题目范围 10^4，平方后 10^8，在 int (2*10^9) 范围内，安全。
        int sqLeft = nums[left] * nums[left];
        int sqRight = nums[right] * nums[right];
        
        if (sqLeft > sqRight) {
            result[pos] = sqLeft;
            left++; // 左指针向右移动
        } else {
            result[pos] = sqRight;
            right--; // 右指针向左移动
        }
        pos--; // 填充位置向前移动
    }
    
    return result;
}

int main() {
    // 提升 cin/cout 速度，NOI 竞赛必备技巧
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (cin >> n) { // 检查输入流状态
        vector<int> nums(n);
        for (int i = 0; i < n; ++i) {
            cin >> nums[i];
        }
        
        // 调用算法
        vector<int> res = sortedSquares(nums);
        
        // 输出结果
        for (int i = 0; i < n; ++i) {
            cout << res[i] << (i == n - 1 ? "" : " ");
        }
        cout << endl;
    }
    
    return 0;
}

希望这个引导过程能帮你彻底理解这道题的精髓！如果有不懂的地方，请随时在草稿纸上再画一次那个“U型”曲线。