LeetCode 280. 摆动排序
题目描述
题意分析
原地重排数组，使相邻关系依次满足
nums[0] <= nums[1] >= nums[2] <= nums[3] ...。使用从0开始的下标，奇数位置是峰，偶数位置是谷。相邻元素允许相等，返回任意满足这些非严格关系的排列即可。只调整原有元素的位置，不增加或删除数值，也不要求数组整体有序。
解法：单次扫描交换
核心思路
[!blue]
从下标
1开始，依次检查当前元素与前一个元素的关系，并保持当前之前的前缀已经摆动有序。若当前下标为奇数，它应不小于前一项；若为偶数，它应不大于前一项。不满足时交换这两个相邻元素即可修好当前关系。关键是交换不会破坏更左边。当前
i为奇数时，只有nums[i] < nums[i - 1]才交换。前一项位于偶数谷位置，交换后它变得更小，原来与再前一个峰之间的“谷不大于峰”关系仍然成立。当前
i为偶数时完全对称：只有当前值比前一项大才交换，前一项是奇数峰位置，交换后它变得更大，原来与更左谷值之间的关系也不会被破坏。一次操作只影响当前相邻对和它左边的一条关系，后者已经证明保持成立，更早位置没有改变。因此每轮都能把合法前缀扩展一格，不需要回头调整，也不需要先做全局排序。相等时已经符合非严格条件，直接保留即可。
解题步骤
- 从下标
i = 1开始向右扫描。i为奇数且当前值小于前一项时，交换两者，让当前位置成为峰。i为偶数且当前值大于前一项时，交换两者，让当前位置成为谷。- 已满足要求则不操作，扫描到最后时原数组已经符合全部相邻关系。
代码实现
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)$，原地操作。
关键点总结
[!green]
- 按当前位置的峰谷角色只修复当前相邻对，而不追求整体排序。
- 修复时会让前一谷更低或前一峰更高，保证已完成的前缀关系不被破坏。
- 非严格不等式允许重复值，因此所有相等情况都能直接通过。
易错点总结
[!yellow]
- 按从一开始的位置编号判断奇偶，会把本实现的峰谷角色颠倒。
- 只处理奇数位置，会漏掉偶数位置过高而破坏下降关系的情况。
- 把要求写成严格小于、大于，会错误地拒绝本题允许的相邻相等。
- Java 交换时不保存旧值，会覆盖一个元素，改变原数组的数值集合。
- 发现一处不满足就重新排序或回退，没有必要；相邻交换的方向已经保证左侧关系保持成立。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 324. 摆动排序 II | 中等 | 本题允许相邻相等，原题要求严格交替且需处理重复值的分布，难点不同。 |
| 面试题 10.11. 峰与谷 | 中等 | 同样构造非严格峰谷序列，可选择局部交换或排序后成对交换。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！