LeetCode 面试题 10.11. 峰与谷
目录
题目描述
题意分析
把数组原地重排成峰谷交替序列。本文采用偶数下标为峰的形式：
nums[0] >= nums[1] <= nums[2] >= nums[3] ...。题目只要求返回任意一种合法排列，峰在奇数位的镜像形式也可以。不等号是非严格的，所以重复元素完全合法；例如
[2,2,2]同时满足两侧关系。若误按 Wiggle Sort II 的严格不等号处理，会给自己增加题目并不存在的难度。排序后相邻元素有确定大小关系，只需交换相邻两项，就能让较大者落在偶数峰位。该方案会修改输入顺序，但题目本来就要求原地重排，不需要保存原下标。
解法：排序后成对交换
核心思路
设排序结果为
a0 <= a1 <= a2 <= a3 ...。交换(a0,a1)、(a2,a3)...后得到a1,a0,a3,a2...。对任意完整的相邻对，偶数位置放该对较大值，所以
nums[2k] >= nums[2k+1]；而下一对的较大值a(2k+3)不小于上一对的较小值a(2k)，所以nums[2k+1] <= nums[2k+2]。两种不等式交替成立，整个数组就是峰谷序列。若数组长度为奇数，最后一个未配对元素是排序后的最大值，落在偶数下标，天然不小于左邻居。长度 0 或 1 时循环不执行，也自然合法。
解题步骤
- 把数组按非降序原地排序。
- 从
i = 0开始，每次步进 2；只要i + 1 < n，交换nums[i]与nums[i+1]。- 奇数长度时最后一项保持原位，无需特判。
以
[5,3,1,2,4]为例，排序得到[1,2,3,4,5]；交换前两对后变为[2,1,4,3,5]。检查关系：2 >= 1 <= 4 >= 3 <= 5，满足峰谷交替。
代码实现
// 排序后让每对中的较大值落在偶数峰位。
class Solution {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 1; i += 2) {
int t = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = t;
}
}
}
// 排序后让每对中的较大值落在偶数峰位。
func wiggleSort(nums []int) {
sort.Ints(nums)
for i := 0; i < len(nums)-1; i += 2 {
nums[i], nums[i+1] = nums[i+1], nums[i]
}
}
复杂度分析
- 时间复杂度：排序占 $O(n \log n)$，成对交换占 $O(n)$，总体 $O(n \log n)$。
- 空间复杂度：交换本身为 $O(1)$；语言库排序可能使用 $O(\log n)$ 递归栈或实现相关辅助空间。
关键点总结
- 先确定峰在哪一类下标，再推导交换方向；本实现让偶数位为峰，因此从下标 0 开始交换每一对。
- 重复值满足非严格峰谷关系，不需要去重或特殊处理。
- 面试追问可以做到 $O(n)$：遍历每个峰位，把它与自己及左右邻居中的最大值交换。排序版更短、更容易一次写对。
- 本题只要求任意合法排列，不要求字典序、稳定性或保留原相对顺序。
易错点总结
- 从下标 1 开始交换却仍按偶数位为峰验证：得到的是镜像方向，若代码与解释不一致会误判正确性。
- 循环写成
i < n后无条件访问i+1：奇数长度时最后一次越界；必须保证i < n-1。- 要求严格大于 / 小于：
[2,2,2]会被误判为无解，而题目允许等号。- 只交换第一对：
[1,2,3,4]变成[2,1,3,4]，末尾3 < 4不满足偶数位 2 为峰的要求。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 280. 摆动排序 | 中等 | 与本题同型，可排序或线性贪心 |
| 324. 摆动排序 II | 中等 | 要求严格不等，重复元素处理更难 |
| 376. 摆动序列 | 中等 | 不重排数组，改为求最长摆动子序列 |