LeetCode 280. 摆动排序
目录
题目描述
题意分析
给定一个无序整数数组，要求原地重排，使它满足
nums[0] <= nums[1] >= nums[2] <= nums[3] >= ...这样的交替关系。函数没有返回值，结果必须写回原数组。最关键的约束信号是不等号非严格：相邻两个元素允许相等。这一条让问题的难度和 324 题（严格版本）拉开了本质差距——非严格意味着任何输入都必然有解，连全部元素相同的数组也天然合法，因此不存在「无解」分支，也不必为重复值设计任何特殊处理。
目标条件本身只约束相邻的两个位置，没有任何跨越多个位置的要求。这是一个很强的结构提示：全局目标可以被拆解成一串独立的局部条件。
输出只要求「某一个合法排列」，不要求字典序最小或与某个特定答案一致，所以解法有很大的自由度。
边界包括：长度为 0 或 1 的数组（天然满足，循环一次都不进）、长度为 2（只需保证前小后大）、以及全部元素相等的数组（原样返回即可）。
解法：单次扫描交换
核心思路
最容易想到的做法是排序后交错填充：把数组排好序，小的一半放偶数下标、大的一半放奇数下标。这确实能构造出合法答案，但代价是 $O(n \log n)$ 的排序，而且通常还要一份额外数组来承接填充结果。
瓶颈在于排序算出了所有元素之间的全序关系，而题目只关心每一对相邻元素的大小关系。这中间隔着巨大的信息浪费。
顺着「条件是局部的」这个特征观察：假设从左到右扫描，前缀
nums[0..i-1]已经排好了摆动关系，现在检查下标i。如果它和左邻居的关系不符合要求，直接把这两个元素交换即可——问题是，交换会不会破坏刚刚建立好的前缀？答案是不会，而且理由很干净。设
i是奇数，要求nums[i] >= nums[i-1]，违反意味着nums[i] < nums[i-1]，交换后新的nums[i-1]变得比原来更小。而i - 1是偶数位，它对左邻居的要求本来就是nums[i-1] <= nums[i-2]，这个条件在前缀里已经成立，值变小之后只会更成立。i是偶数时完全对称：交换让nums[i-1]变大，而它作为奇数位要求nums[i-1] >= nums[i-2]，变大同样不会破坏。也就是说，每次交换都把
nums[i-1]朝着「它自身约束更宽松的方向」推，前缀因此始终安全。由此得到扫描的不变量：处理完下标i之后，nums[0..i]整体满足摆动关系。扫描到末尾时不变量覆盖整个数组，答案即成立。
解题步骤
- 从下标 1 开始向右扫描。下标 0 没有左邻居，不受任何约束，因此循环起点必须是 1，从 0 开始会访问到
nums[-1]。- 当
i为奇数时，该位置是「峰」，要求nums[i] >= nums[i-1]。判断这个关系是否被违反，即检查nums[i] < nums[i-1]。- 当
i为偶数时，该位置是「谷」，要求nums[i] <= nums[i-1]。对应的违反条件是nums[i] > nums[i-1]。- 一旦对应关系被违反，就交换
nums[i]与nums[i-1]。根据上面的论证，这次交换必然修复当前这一对，同时不会破坏i-1与i-2之间已经成立的关系，所以交换后不需要回头重新检查。- 扫描结束时整个数组已经就地满足摆动关系，无需任何收尾操作。
以
[3, 5, 2, 1, 6, 4]走一遍：初始数组[3, 5, 2, 1, 6, 4]。i = 1是奇数，要求nums[1] >= nums[0]，即 $5 \ge 3$ 成立，不交换。i = 2是偶数，要求nums[2] <= nums[1]，即 $2 \le 5$ 成立，不交换。i = 3是奇数，要求nums[3] >= nums[2]，而 $1 < 2$ 被违反，交换下标 2 和 3，数组变成[3, 5, 1, 2, 6, 4]；此时回看下标 2 的约束nums[2] <= nums[1]，$1 \le 5$ 依然成立，前缀安全。i = 4是偶数，要求nums[4] <= nums[3]，而 $6 > 2$ 被违反，交换下标 3 和 4，数组变成[3, 5, 1, 6, 2, 4]；回看下标 3 的约束nums[3] >= nums[2]，$6 \ge 1$ 成立。i = 5是奇数，要求nums[5] >= nums[4]，$4 \ge 2$ 成立，不交换。最终结果[3, 5, 1, 6, 2, 4]，逐对验证 $3 \le 5$、$5 \ge 1$、$1 \le 6$、$6 \ge 2$、$2 \le 4$，全部满足。
代码实现
class Solution {
// 从左到右维护已经处理好的前缀，只需要检查当前元素和前一个元素是否满足当前位置的关系。
public void wiggleSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if ((i % 2 == 1 && nums[i] < nums[i - 1])
|| (i % 2 == 0 && nums[i] > nums[i - 1])) {
int current = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = current;
}
}
}
}
func wiggleSort(nums []int) {
// 从左到右维护已经处理好的前缀，只需要检查当前元素和前一个元素是否满足当前位置的关系。
for i := 1; i < len(nums); i++ {
if (i%2 == 1 && nums[i] < nums[i-1]) || (i%2 == 0 && nums[i] > nums[i-1]) {
nums[i], nums[i-1] = nums[i-1], nums[i]
}
}
}
复杂度分析
- 时间复杂度：$O(n)$，只做一趟从左到右的扫描，每个下标处至多一次比较和一次交换，扫描指针从不回退。
- 空间复杂度：$O(1)$，全程在原数组上就地交换，只用了一个循环变量和交换时的临时变量，没有排序也没有辅助数组。
关键点总结
- 判断一道重排题能否用「局部修复」线性解决，看两点：目标条件是否只约束相邻元素，以及修复动作会不会破坏已经建立好的前缀。本题两点都成立，所以排序是多余的。
- 交换的安全性必须证明而不是凭感觉。奇数位的交换让左邻居变小，而左邻居作为偶数位本来就要求「不大于它的左邻」，变小只会更成立；偶数位完全对称。这个对称性是整道题的技术核心。
- 不等号严不严格决定了题目属于哪一类。非严格版本可以贪心线性解决，改成严格（324 题）后相邻交换立刻失效，必须转向中位数划分加逆序交错填充。拿到题先看不等号。
- 交换之后不需要回退重查。前缀不变量已经保证了安全性，回退只会平白增加常数甚至把复杂度推高。
- 面试视角：面试官往往先接受 $O(n \log n)$ 的排序交错，然后追问「能不能做到线性」。这题的全部含金量就在于你能否现场把「交换不破坏前缀」这一步讲清楚，光给出代码而说不出理由，会被判定成背题。
- 面试视角：常见的延伸追问是「如果要求严格不等呢」。要能立刻举出
[2, 2]这种无解输入，说明严格版本首先要判可行性，再指向排序后逆序交错的构造方式。
易错点总结
- 错误写法：奇偶位的判据方向写反，把奇数位当成「谷」。用例
[1, 2]→i = 1处误判为需要nums[1] <= nums[0]，触发交换得到[2, 1]，而题目要求nums[0] <= nums[1]，直接判错。- 错误写法：把下标 0 当作「第 1 位」来算奇偶，用
i % 2 == 0判断峰。用例[1, 2]→i = 1被归为谷位，同样交换成[2, 1]，正确结果是保持[1, 2]。- 错误写法：循环从
i = 0起步。用例 任意非空数组 → 第一轮就访问nums[-1]，下标越界抛异常；下标 0 没有左邻居，本就无需检查。- 错误写法：只检查奇数位，跳过偶数位的约束。用例
[1, 2, 3]→i = 1处 $2 \ge 1$ 通过，i = 2因未检查而原样保留，结果[1, 2, 3]中nums[1] = 2并不大于等于nums[2] = 3，正确结果形如[1, 3, 2]。- 错误写法：交换时漏掉临时变量，写成
nums[i] = nums[i-1]; nums[i-1] = nums[i];。用例[2, 1]→ 第一句就把nums[i]覆盖成 2，第二句再赋回去，两个位置都变成 2，原数据被破坏。- 错误写法：交换之后执行
i--回退重查。用例[3, 5, 2, 1, 6, 4]→ 每次交换都要多走一轮已经确认安全的比较，白白抬高常数，构造出的最坏输入会把复杂度推到 $O(n^2)$。- 错误写法：把结果构造在一个新数组里返回，忘记写回
nums。用例 任意输入 → 判题读取的是原数组，内容完全没变，直接判错；接口返回void的题目一定要检查最终写回。- 错误写法：套用 324 题的严格版解法，先排序再逆序交错。用例
[3, 5, 2, 1, 6, 4]→ 结果虽然合法，但复杂度从 $O(n)$ 退回 $O(n \log n)$ 且多占 $O(n)$ 空间，一旦被追问「能否线性、能否常数空间」就答不上来。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 324. 摆动排序 II | 中等 | 不等号变为严格，相邻交换彻底失效，必须排序后从两半逆序交错填充 |
| 376. 摆动序列 | 中等 | 不允许重排，求原序列中最长摆动子序列的长度，靠贪心记录方向翻转 |
| 905. 按奇偶排序数组 | 简单 | 只要求偶数全部排在奇数之前，是分区问题而非交替大小关系 |
| 922. 按奇偶排序数组 II | 简单 | 要求数值的奇偶性与下标奇偶性对应，用双指针配对修正而非相邻交换 |