LeetCode 面试题 10.11. 峰与谷
题目描述
题意分析
把数组原地重排成峰谷交替序列。本文采用偶数下标为峰的形式：
nums[0] >= nums[1] <= nums[2] >= nums[3] ...。题目只要求返回任意一种合法排列，峰在奇数位的镜像形式也可以。峰只需不小于相邻元素，谷只需不大于相邻元素，不等号都是非严格的，所以重复值可以相邻。数组两端只有一个邻居，只需满足这一侧的关系。
排序后相邻元素有确定大小关系，只需交换相邻两项，就能让较大者落在偶数峰位。该方案会修改输入顺序，但题目本来就要求原地重排，不需要保存原下标。
解法：排序后成对交换
核心思路
[!blue]
先排序，让所有元素满足
a0 <= a1 <= a2 <= a3 ...。再把相邻的两个元素作为一组，交换每组内部的顺序，得到a1,a0,a3,a2...。这样每组都把较大的值放在偶数峰位，较小的值放在奇数谷位。需要分别检查组内与组间两种相邻关系。组内由交换保证
nums[2k] >= nums[2k + 1]；组间由于后一组原本排在前一组之后，后一组的峰值也不小于前一组的谷值，所以nums[2k + 1] <= nums[2k + 2]。这两类关系覆盖了全部相邻位置，因此整个数组都满足峰谷交替。若数组长度为奇数，最后一个未配对元素是排序后的最大值，落在偶数下标，天然不小于左邻居。长度 0 或 1 时循环不执行，也自然合法。
解题步骤
- 把数组按非降序原地排序。
- 从
i = 0开始，每次步进 2；只要i + 1 < n，交换nums[i]与nums[i+1]。- 奇数长度时最后一项保持原位，无需特判。
每轮只交换当前相邻对，不会再改变已经处理的组。循环每次前进两格，在没有完整的一对时结束；排序和交换都在原数组上操作，函数无需构建或返回另一个数组。
代码实现
// 排序后让每对中的较大值落在偶数峰位。
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;
}
}
}
import (
"sort"
)
// 排序后让每对中的较大值落在偶数峰位。
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)$ 递归栈或实现相关辅助空间。
关键点总结
[!green]
- 先确定峰在哪一类下标，再推导交换方向；本实现让偶数位为峰，因此从下标 0 开始交换每一对。
- 重复值满足非严格峰谷关系，不需要去重或特殊处理。
- 排序提供跨组大小关系，成对交换提供组内大小关系，正确性需要同时检查这两部分。
- 本题只要求任意合法排列，不要求字典序、稳定性或保留原相对顺序。
易错点总结
[!yellow]
- 从下标 1 开始交换却仍按偶数位为峰验证：得到的是镜像方向，若代码与解释不一致会误判正确性。
- 循环写成
i < n后无条件访问i+1：奇数长度时最后一次越界；必须保证i < n-1。- 要求严格大于 / 小于：相同元素可能导致严格摆动无解，但本题允许等号。
- 只交换第一对：后面的完整分组仍保持升序，不能保证所有偶数位置都是峰。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 324. 摆动排序 II | 中等 | 原题要求严格交替且需妥善分散重复值，本题允许相等，排序后相邻交换即可。 |
| 280. 摆动排序 | 中等 | 同样是非严格摆动排列，可对比只按相邻关系线性调整的实现。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！