LeetCode 896. 单调数列
题目描述
题意分析
判断原数组是否整体非递减，或者整体非递增；两种方向只需满足一种，相等的元素不会破坏单调性。
不必比较任意两个位置。如果每对相邻元素都满足前者不大于后者，由大小关系的传递性，任意更靠前的元素也不会大于更靠后的元素；非递增同理。因此只检查相邻关系就足够了。
解法：分别排除两种单调方向
核心思路
[!blue]
用
increasing表示已经扫描的前缀仍然非递减，用decreasing表示它仍然非递增。最开始还没有相邻关系，两种方向都没有被否定，所以都初始化为true。扫描到
nums[i]时，如果它小于前一个元素，就出现下降，非递减方向被排除；如果它大于前一个元素，就出现上升，非递增方向被排除；相等则两种方向都可以保留。标记一旦变为false就不能恢复，因为后面的元素无法消除已经出现的反例。每轮只增加一对新的相邻关系，因此更新后，两个标记仍准确描述整个已扫描前缀。扫描结束时，它们就分别代表整个数组是否非递减、是否非递增，返回逻辑或即可；两者都为假才说明数组同时出现过上升和下降。
解题步骤
- 将两个方向标记设为 true。
- 扫描每对相邻元素，按大小关系更新标记。
- 返回两个标记的逻辑或。
单元素数组没有需要比较的相邻项，会保留两个真值；全相等数组也不会排除任何方向，所以这两类输入都自然返回
true。开头有多项相等时，同样不必提前决定方向。
代码实现
class Solution {
public boolean isMonotonic(int[] nums) {
boolean increasing = true;
boolean decreasing = true;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
increasing = false;
}
if (nums[i] > nums[i - 1]) {
decreasing = false;
}
}
return increasing || decreasing;
}
}
func isMonotonic(nums []int) bool {
increasing, decreasing := true, true
for i := 1; i < len(nums); i++ {
if nums[i] < nums[i-1] {
increasing = false
}
if nums[i] > nums[i-1] {
decreasing = false
}
}
return increasing || decreasing
}
复杂度分析
- 时间复杂度：$O(n)$，每对相邻元素只比较一次。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
- 相邻关系通过传递性保证全局单调，无需两两比较所有元素。
- 两个标记记录尚未被反例排除的方向，更新只能从真变假。
- 同时保留两种可能性，统一处理开头相等和全相等的情况。
易错点总结
[!yellow]
- 非严格单调允许相等，不能把相等当成失败。
- 最后返回逻辑或，不能要求两个方向同时成立；后者只会接受全相等数组。
- 一次上升或下降只能排除相反方向，不能把另一方向重新设为真。
- 排序后再检查会丢掉原顺序，无法回答本题。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 941. 有效的山脉数组 | 简单 | 都根据相邻升降关系扫描；山脉要求先严格升后严格降，本题要求整段只有一个非严格方向。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！