LeetCode 977. 有序数组的平方

约 4 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 字节 阿里 小米
标签
数组 排序 双指针

题目描述

✅ 977. 有序数组的平方

image-20260928215856921

题意分析

给定一个按非递减顺序排列的整数数组，将每个元素平方，返回同样按非递减顺序排列的新数组。每次出现都要保留，原数组中的重复值或平方后相等的值，也要按原有数量写入结果。

原数组可能包含负数、零和正数。负数越小，绝对值可能越大，所以逐项平方并不能保证结果仍然有序。题目进阶要求线性时间，应利用输入已经有序这一条件，而不是平方后重新排序。

解法：双指针倒序填充

核心思路

[!blue]

平方的大小由绝对值决定。对于剩余的有序区间，若全是负数，最左端绝对值最大；若全是非负数，最右端最大；若跨过零，最大绝对值仍只能来自最左的负数或最右的正数。因此只比较两个端点的平方，就能找到剩余元素中的最大平方。

用 left、right 表示尚未处理的区间，每次取较大的端点平方，放进结果最后一个空位置 pos。因为取得的是最大值，写入方向必须从后向前；已经写好的后缀都是最终位置，不需要再参与比较。

写入后只移动提供这个平方值的那个指针，表示消费了原数组中的一次出现，再将 pos 向前移动。若两端平方相等，任选一端写入即可，另一个元素仍留在区间内等待后续处理，不能同时丢掉。

每轮开始时，尚未处理的元素数量恰好等于结果空位置的数量。循环让 pos 从 n - 1 走到 0，一共写入 n 次；最后左右指针相遇时仍有一个值要处理。由每次把剩余最大值放到最右空位，最终结果自然非递减，也完整保留全部元素。

解题步骤

  1. 创建长度为 n 的结果数组，初始化 left = 0、right = n - 1。
  2. 让写入位置 pos 从 n - 1 递减到 0，分别计算两端平方。
  3. 较大平方写入 res[pos]，只移动对应的端点；相等时任选一端。
  4. 所有位置写满后返回结果数组，原数组不需要修改。

代码实现

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 0;
        int right = n - 1;

        for (int pos = n - 1; pos >= 0; pos--) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];

            if (leftSquare > rightSquare) {
                // 最大平方值放到当前最后的空位。
                res[pos] = leftSquare;
                left++;
            } else {
                res[pos] = rightSquare;
                right--;
            }
        }

        return res;
    }
}

func sortedSquares(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    left := 0
    right := n - 1
    for pos := n - 1; pos >= 0; pos-- {
        leftSquare := nums[left] * nums[left]
        rightSquare := nums[right] * nums[right]
        if leftSquare > rightSquare {
            // 原数组两端产生当前最大的平方值。
            res[pos] = leftSquare
            left++
        } else {
            res[pos] = rightSquare
            right--
        }
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，每轮消费一个元素并填入一个结果位置，共执行 n 轮。
  • 空间复杂度：返回数组占 $O(n)$；不计返回结果时，只使用两个端点和写入下标，辅助空间为 $O(1)$。

关键点总结

[!green]

  • 有序区间的最大绝对值在两端，端点平方比较即可确定剩余最大值。
  • 每次取得最大值，所以结果从右向左填充。
  • 每轮只消费一个元素，即使两端平方相等也要分别保留其出现次数。

易错点总结

[!yellow]

  • 直接比较原数值大小，会忽略负数绝对值较大时的平方。
  • 把每次选出的较大值从前向后写，会得到降序结果。
  • 两端平方相等时同时移动两个指针，却只写一个位置，会丢失一次出现。
  • 使用 left < right 就结束循环，会漏掉两指针相遇后的最后一个元素；按结果位置循环能自然覆盖它。
  • 直接在原数组末尾覆盖答案，可能覆盖还没有被消费的输入值；这里使用独立结果数组。

相似题目

题目 难度 关联与区别
360. 有序转化数组 中等 平方是二次函数特例，原题还需根据二次项符号选择从两端填最大还是最小值。
88. 合并两个有序数组 简单 平方后负数段逆序、非负段正序，可视为两条有序序列的归并。
补充题 160. 有序数组的不同平方值计数 中等 都比较有序数组两端的绝对值；补充题跳过相同绝对值，只统计不同平方。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/00756785
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！