LeetCode 补充题 113. 先升后降数组的线性排序
题目描述
给你一个先非降序、后非升序的整数数组
nums。数组允许包含重复值，也允许其中一段为空。请在
O(n)时间内返回一个按非降序排列的新数组，保留输入中的全部元素。其中n是数组长度。
示例 1：
输入：
nums = [1,4,7,6,2]
输出：[1,2,4,6,7]
解释： 输入先升后降，结果按非降序排列，所有元素均保留。
提示：
- 数组先非降序、后非升序，允许重复值及一侧为空。
- 要求
O(n)时间，返回新数组。
题意分析
通用排序没有利用先升后降的结构。从左端朝峰顶看是非降序，从右端朝峰顶看也同样非降序，因此可以像归并两个有序来源一样，每次输出当前较小的一端。
解法：从两端归并到峰顶
核心思路
[!blue]
对任意剩余区间
[left,right]，峰顶左侧的元素都不小于左端，峰顶右侧的元素都不小于右端。若峰顶已在区间外，整个区间单调，最小值也在端点。因此剩余最小值必然是两个端点之一。比较两端后输出较小值，只移动对应指针，剩余区间仍保留先升后降的性质，这个结论可以反复使用。相等时任选一端，不做去重，保证每个输入元素恰好输出一次。
总共写入
n项后结束，不会再访问已经交错的指针；空数组的循环不执行，返回空结果。整个过程不需要先寻找峰顶。
解题步骤
- 左右指针分别放在数组两端，分配结果数组。
- 每次比较两端，取较小值写入结果并推进该侧。
- 恰好取完全部元素，重复值全部保留。
代码实现
class Solution {
public int[] sortMountain(int[] a) {
int[] out = new int[a.length];
int left = 0;
int right = a.length - 1;
for (int i = 0; i < out.length; i++) {
out[i] = a[left] <= a[right] ? a[left++] : a[right--];
}
return out;
}
}
func sortMountain(a []int) []int {
out := make([]int, len(a))
left, right := 0, len(a)-1
for i := range out {
if a[left] <= a[right] {
out[i] = a[left]
left++
} else {
out[i] = a[right]
right--
}
}
return out
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：结果数组空间 $O(n)$，除结果外额外空间 $O(1)$。
关键点总结
[!green]
任意剩余区间仍是先升后降，最小值只能在端点，因此不需要先寻找峰顶。
易错点总结
[!yellow]
输入必须满足先升后降；普通无序数组的最小值不一定在两端。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 88. 合并两个有序数组 | 简单 | 把朝峰顶的两侧视为两条有序流，按较小端依次归并。 |
| 977. 有序数组的平方 | 简单 | 同样从数组两端提取极值；平方数组从两端取最大，本题山形数组从两端取最小。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！