LeetCode 896 Monotonic Array 单调数组判定三种解法详解与多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读单调数组Monotonic Array是 LeetCode 第 896 题也是数组遍历与相邻元素比较类问题中最具代表性的入门题之一。本文以仓库文档 articles/monotonic-array.md 为核心骨架完整讲解双扫描Two Pass、单次扫描 IOne Pass I、单次扫描 IIOne Pass II三种解法的直觉、算法步骤、时间/空间复杂度与常见陷阱并对照仓库中 python/0896-monotonic-array.py、java/0896-monotonic-array.java、kotlin/0896-monotonic-array.kt、swift/0896-monotonic-array.swift 等源码实现逐一印证。读完本文你将掌握非递减 / 非递增判定中相等元素的正确处理方式并能独立写出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的通过版本。问题定义与前置知识题目要求给定整数数组nums判断它是否单调。若数组整体非递减nums[i] nums[i1]恒成立或整体非递增nums[i] nums[i1]恒成立则视为单调数组。前置知识原文档明确要求数组Arrays理解如何遍历数组并按索引访问元素比较运算符Comparison Operators使用比较运算符检查相邻元素之间的大小关系。关键语义单调数组允许相邻元素相等。非递减对应非递增对应。因此[1, 2, 2, 3]是单调数组[5, 5, 5]同时满足非递减与非递增也应返回true。这一语义贯穿三种解法也是本题最容易出错的地方。1. 解法一双扫描Two Pass直觉一个数组是单调的当且仅当它整体非递减或整体非递增。因此可以分别检查两种条件先扫描一次检查是否每个元素都大于等于前一个元素非递减若成立则数组单调递增直接返回true若不成立再扫描一次检查是否每个元素都小于等于前一个元素非递增返回第二次检查的结果。由于两次检查各自独立、互不干扰即使第一次失败第二次仍可能成功——这正是处理[5, 5, 5]、[1, 2, 2, 3]这类数组的关键。算法步骤假设数组递增令increase true遍历i从1到n-1若发现nums[i] nums[i-1]则置increase false并跳出循环若increase仍为true返回true否则假设数组递减令decrease true遍历i从1到n-1若发现nums[i] nums[i-1]则置decrease false并跳出循环返回decrease。多语言实现Pythonclass Solution: def isMonotonic(self, nums: List[int]) - bool: n len(nums) increase True for i in range(1, n): if nums[i] nums[i - 1]: increase False break if increase: return True decrease True for i in range(1, n): if nums[i] nums[i - 1]: decrease False break return decreaseJavapublic class Solution { public boolean isMonotonic(int[] nums) { int n nums.length; boolean increase true; for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { increase false; break; } } if (increase) { return true; } boolean decrease true; for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { decrease false; break; } } return decrease; } }Cclass Solution { public: bool isMonotonic(vectorint nums) { int n nums.size(); bool increase true; for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { increase false; break; } } if (increase) { return true; } bool decrease true; for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { decrease false; break; } } return decrease; } };JavaScriptclass Solution { /** * param {number[]} nums * return {boolean} */ isMonotonic(nums) { const n nums.length; let increase true; for (let i 1; i n; i) { if (nums[i] nums[i - 1]) { increase false; break; } } if (increase) { return true; } let decrease true; for (let i 1; i n; i) { if (nums[i] nums[i - 1]) { decrease false; break; } } return decrease; } }C#public class Solution { public bool IsMonotonic(int[] nums) { int n nums.Length; bool increase true; for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { increase false; break; } } if (increase) { return true; } bool decrease true; for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { decrease false; break; } } return decrease; } }Gofunc isMonotonic(nums []int) bool { n : len(nums) increase : true for i : 1; i n; i { if nums[i] nums[i-1] { increase false break } } if increase { return true } decrease : true for i : 1; i n; i { if nums[i] nums[i-1] { decrease false break } } return decrease }Kotlinclass Solution { fun isMonotonic(nums: IntArray): Boolean { val n nums.size var increase true for (i in 1 until n) { if (nums[i] nums[i - 1]) { increase false break } } if (increase) { return true } var decrease true for (i in 1 until n) { if (nums[i] nums[i - 1]) { decrease false break } } return decrease } }Swiftclass Solution { func isMonotonic(_ nums: [Int]) - Bool { let n nums.count var increase true for i in 1..n { if nums[i] nums[i - 1] { increase false break } } if increase { return true } var decrease true for i in 1..n { if nums[i] nums[i - 1] { decrease false break } } return decrease } }Rustimpl Solution { pub fn is_monotonic(nums: Veci32) - bool { let n nums.len(); let mut increase true; for i in 1..n { if nums[i] nums[i - 1] { increase false; break; } } if increase { return true; } let mut decrease true; for i in 1..n { if nums[i] nums[i - 1] { decrease false; break; } } decrease } }复杂度分析时间复杂度$O(n)$——最坏情况下两趟完整扫描每趟 $O(n)$合起来仍是 $O(n)$空间复杂度$O(1)$——只使用常数个布尔标志。2. 解法二单次扫描 IOne Pass I直觉双扫描在最坏情况下要遍历两遍。能否先确定方向、只扫一遍可以比较首尾元素即可预判整体趋势——若nums[0] nums[n-1]说明数组整体应当非递减否则应当非递增。方向确定后一趟遍历即可验证所有相邻对是否都符合预期模式。需要注意首尾比较确定的是整体趋势而不是严格单调。中间即使出现相等元素也不影响因为判定条件本身就是非严格比较。算法步骤比较nums[0]与nums[n-1]确定预期方向若nums[0] nums[n-1]数组应为非递减遍历i从1到n-1一旦发现nums[i] nums[i-1]立即返回false否则数组应为非递增遍历i从1到n-1一旦发现nums[i] nums[i-1]立即返回false未发现任何违反返回true。多语言实现Pythonclass Solution: def isMonotonic(self, nums: List[int]) - bool: n len(nums) if nums[0] nums[-1]: for i in range(1, n): if nums[i] nums[i - 1]: return False return True else: for i in range(1, n): if nums[i] nums[i - 1]: return False return TrueJavapublic class Solution { public boolean isMonotonic(int[] nums) { int n nums.length; if (nums[0] nums[n - 1]) { for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { return false; } } return true; } else { for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { return false; } } return true; } } }Cclass Solution { public: bool isMonotonic(vectorint nums) { int n nums.size(); if (nums[0] nums[n - 1]) { for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { return false; } } return true; } else { for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { return false; } } return true; } } };JavaScriptclass Solution { /** * param {number[]} nums * return {boolean} */ isMonotonic(nums) { const n nums.length; if (nums[0] nums[n - 1]) { for (let i 1; i n; i) { if (nums[i] nums[i - 1]) { return false; } } return true; } else { for (let i 1; i n; i) { if (nums[i] nums[i - 1]) { return false; } } return true; } } }C#public class Solution { public bool IsMonotonic(int[] nums) { int n nums.Length; if (nums[0] nums[n - 1]) { for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { return false; } } return true; } else { for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { return false; } } return true; } } }Gofunc isMonotonic(nums []int) bool { n : len(nums) if nums[0] nums[n-1] { for i : 1; i n; i { if nums[i] nums[i-1] { return false } } return true } else { for i : 1; i n; i { if nums[i] nums[i-1] { return false } } return true } }Kotlinclass Solution { fun isMonotonic(nums: IntArray): Boolean { val n nums.size if (nums[0] nums[n - 1]) { for (i in 1 until n) { if (nums[i] nums[i - 1]) { return false } } return true } else { for (i in 1 until n) { if (nums[i] nums[i - 1]) { return false } } return true } } }Swiftclass Solution { func isMonotonic(_ nums: [Int]) - Bool { let n nums.count if nums[0] nums[n - 1] { for i in 1..n { if nums[i] nums[i - 1] { return false } } return true } else { for i in 1..n { if nums[i] nums[i - 1] { return false } } return true } } }Rustimpl Solution { pub fn is_monotonic(nums: Veci32) - bool { let n nums.len(); if nums[0] nums[n - 1] { for i in 1..n { if nums[i] nums[i - 1] { return false; } } true } else { for i in 1..n { if nums[i] nums[i - 1] { return false; } } true } } }复杂度分析时间复杂度$O(n)$——仅一趟遍历且命中违反时可提前返回空间复杂度$O(1)$。3. 解法三单次扫描 IIOne Pass II直觉解法二通过首尾元素预判方向但预判本身也是一种开销较小的技巧更直接的做法是同时跟踪两种可能性维护两个标志——一个表示数组仍可能非递减一个表示仍可能非递增。扫描过程中任何违反都会取消对应方向。最后只要至少一个标志仍为true数组就是单调的。这种双标志同时维护的写法最简洁也最不容易漏掉[5, 5, 5]这类特殊情况因为它天然同时考虑了两个方向。算法步骤初始化两个布尔标志increase truedecrease true遍历相邻对(nums[i], nums[i1])若nums[i] nums[i1]置increase false若nums[i] nums[i1]置decrease false返回increase || decrease。多语言实现Pythonclass Solution: def isMonotonic(self, nums: List[int]) - bool: increase, decrease True, True for i in range(len(nums) - 1): if not (nums[i] nums[i 1]): increase False if not (nums[i] nums[i 1]): decrease False return increase or decreaseJavapublic class Solution { public boolean isMonotonic(int[] nums) { boolean increase true, decrease true; for (int i 0; i nums.length - 1; i) { if (!(nums[i] nums[i 1])) { increase false; } if (!(nums[i] nums[i 1])) { decrease false; } } return increase || decrease; } }Cclass Solution { public: bool isMonotonic(vectorint nums) { bool increase true, decrease true; for (int i 0; i nums.size() - 1; i) { if (!(nums[i] nums[i 1])) { increase false; } if (!(nums[i] nums[i 1])) { decrease false; } } return increase || decrease; } };JavaScriptclass Solution { /** * param {number[]} nums * return {boolean} */ isMonotonic(nums) { let increase true, decrease true; for (let i 0; i nums.length - 1; i) { if (!(nums[i] nums[i 1])) { increase false; } if (!(nums[i] nums[i 1])) { decrease false; } } return increase || decrease; } }C#public class Solution { public bool IsMonotonic(int[] nums) { bool increase true, decrease true; for (int i 0; i nums.Length - 1; i) { if (!(nums[i] nums[i 1])) { increase false; } if (!(nums[i] nums[i 1])) { decrease false; } } return increase || decrease; } }Gofunc isMonotonic(nums []int) bool { increase, decrease : true, true for i : 0; i len(nums)-1; i { if !(nums[i] nums[i1]) { increase false } if !(nums[i] nums[i1]) { decrease false } } return increase || decrease }Kotlinclass Solution { fun isMonotonic(nums: IntArray): Boolean { var increase true var decrease true for (i in 0 until nums.size - 1) { if (!(nums[i] nums[i 1])) { increase false } if (!(nums[i] nums[i 1])) { decrease false } } return increase || decrease } }Swiftclass Solution { func isMonotonic(_ nums: [Int]) - Bool { var increase true var decrease true for i in 0..(nums.count - 1) { if !(nums[i] nums[i 1]) { increase false } if !(nums[i] nums[i 1]) { decrease false } } return increase || decrease } }Rustimpl Solution { pub fn is_monotonic(nums: Veci32) - bool { let mut increase true; let mut decrease true; for i in 0..nums.len() - 1 { if nums[i] nums[i 1] { increase false; } if nums[i] nums[i 1] { decrease false; } } increase || decrease } }复杂度分析时间复杂度$O(n)$——严格一趟扫描空间复杂度$O(1)$。常见陷阱Common Pitfalls原文档明确指出本题最容易踩的两个坑值得单独强调陷阱一把非严格比较误写成严格比较单调数组允许相邻元素相等即允许非递减或非递增。若误用严格比较例如用nums[i] nums[i-1]代替nums[i] nums[i-1]会把[1, 2, 2, 3]这类含相等相邻元素的合法单调数组错误地判为不单调。正确写法应检查非递减或非递增来正确处理相等的相邻值。陷阱二只检查单一方向所有元素都相等的数组如[5, 5, 5]同时满足非递减和非递增应返回true。若在某个方向发现违反后不做另一方向的检查就提前返回false就会得到错误结果——例如只按严格递增或严格递减去匹配的模式必然漏掉这种情况。解法三的双标志写法恰好从结构上规避了这一陷阱。三种解法对比与选择解法扫描次数提前返回代码量适用场景解法一Two Pass最坏 2 次递增检查通过后提前返回中等思路最直观适合讲解阶段解法二One Pass I1 次命中违反立即返回中等想省一次遍历、又偏好显式方向判断解法三One Pass II1 次无须扫完最少最简洁双标志天然覆盖相等元素三者时间均为 $O(n)$、空间均为 $O(1)$在数据量增大时性能表现一致选择标准主要看代码可读性与个人偏好。仓库源码印证仓库中已经收录了本题的多种语言实现可直接对照阅读python/0896-monotonic-array.py采用解法三思路increasing decreasing True遇到nums[i] nums[i1]取消递增、nums[i] nums[i1]取消递减最终return increasing or decreasing与本文解法三完全一致java/0896-monotonic-array.java同样以inc、dec双标志实现解法三kotlin/0896-monotonic-array.kt采用了不同的变体——先比较首尾元素nums[nums.lastIndex] - nums[0] 0若整体趋势为下降则先reverse()再统一按非递减方向做单趟校验。这实际上是解法二思路的一种 Kotlin 风格实现从源码结构可以推断它依赖 Kotlin 标准库的原地反转能力swift/0896-monotonic-array.swift与解法三一致的双标志实现并带有题目链接注释。可见仓库对同一道题保留了多种思路的实现Python/Java/Swift 体现解法三Kotlin 体现解法二的变体而 articles/monotonic-array.md 则完整收录了三种思路的九语言版本覆盖更全面。读者可将文档中的伪代码/完整实现与仓库源码相互对照理解同一算法在不同语言、不同惯用法下的落地形态。边界用例自测清单在提交前建议用以下用例快速验证三种实现[1, 2, 2, 3]→true含相等元素的非递减[6, 5, 4, 4]→true含相等元素的非递增[5, 5, 5]→true常数数组两个方向同时成立[1, 3, 2]→false先升后降[1]→true单元素数组两种方向都真空满足[]→true空数组同样满足遍历区间为空时标志保持true。这些用例同时覆盖了原文档强调的两大陷阱严格比较、单一方向是检验实现正确性的最小完备集合。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考