- 正确答案：遍历数组一次，分别检查是否满足非递减（正序）或非递增（倒序）性质；若至少一种成立，则数组有序。更高效的做法是：先跳过开头相等元素，确定初始单调方向（上升或下降），再验证后续所有相邻对是否保持该方向。时间复杂度 O(n)，空间复杂度 O(1)。 - 解答思路：第一步：处理边界情况——空数组、单元素数组、全相同元素数组均视为有序（数学上，非递减和非递增同时成立）。第二步：从左向右扫描，找到第一个相邻不等的位置 (i, i+1)，据此判断预期方向：若 arr[i] < arr[i+1]，则应为非递减序列；若 arr[i] > arr[i+1]，则应为非递增序列。第三步：按已确定的方向继续遍历剩余部分，一旦出现违反方向的相邻对（如已定为非递减，却遇到 arr[j] > arr[j+1]），立即返回 false。第四步：若遍历完成无矛盾，返回 true。注意：不能分别独立检查“是否非递减”和“是否非递增”再取或（即 is_sorted_asc || is_sorted_desc），虽然逻辑正确，但最坏需遍历两次；而单次遍历判定更优，符合工程中对常数因子的敏感性要求。 - 深度知识讲解：本题表面是简单遍历，实则考察对“有序”定义的精确理解、边界鲁棒性设计、以及算法常数优化意识。 ▶ 底层知识点一：数组有序性的数学定义。 “有序（正序或倒序）”在算法题中通常指“非递减”或“非递增”，而非严格递增/递减——因允许重复元素。这是由实际场景决定的（如成绩排名并列、时间戳重复等）。严格单调性（strictly increasing/decreasing）需用 > / < 判断，而非 >= / <=。 ▶ 底层知识点二：比较模型与决策树下界。判定任意数组是否有序，信息论下界为 Ω(n)：必须至少读取每个元素一次（反例：若跳过某 arr[k]，构造 arr[k−1]=arr[k+1]=0，而 arr[k] 可为任意值，即可破坏单调性）。因此 O(n) 是理论最优，不存在亚线性解法。 ▶ 底层知识点三：缓存友好性与分支预测。单次遍历方案具有良好空间局部性（顺序访问内存），CPU 预取器可高效工作；而双路检查（先扫一遍升序、再扫一遍降序）会增加 cache miss 概率，且 if 分支更多（两次 loop + 两次条件判断），现代 CPU 分支预测失败代价显著。 ▶ 底层知识点四：“方向未定”状态机建模。可将算法抽象为三态有限自动机： state = UNKNOWN → 遇 arr[i] < arr[i+1] → state = ASC state = UNKNOWN → 遇 arr[i] > arr[i+1] → state = DESC state = UNKNOWN → 遇 arr[i] == arr[i+1] → 保持 UNKNOWN state = ASC → 要求 arr[j] <= arr[j+1]，否则 reject state = DESC → 要求 arr[j] >= arr[j+1]，否则 reject 这种状态机视角有助于写出无逻辑漏洞的代码，尤其在并发或流式数据（如 iterator）场景下可自然扩展为在线算法。 - 伪代码（带注释）： function isMonotonic(arr): n = length(arr) if n <= 2: return true // 0/1/2 个元素必有序（含全等情形） // 状态机初始化 direction = UNKNOWN // 可取值：UNKNOWN, ASC, DESC for i from 0 to n-2: if arr[i] < arr[i+1]: if direction == DESC: return false direction = ASC else if arr[i] > arr[i+1]: if direction == ASC: return false direction = DESC // 若相等，direction 保持不变，无需操作 return true - 补充说明与易错点： ✅ 正确处理全等数组：上述代码中所有相等情况均不改变 direction，循环结束后 direction 仍为 UNKNOWN，最终返回 true —— 符合定义。 ❌ 常见错误写法：用 flag = 0/1/2 编码方向，但未在相等时跳过判断，导致误判；或在发现第一个不等对后强行 break 并只验证剩余部分，却忽略后续可能再次出现反向不等对（实际不会，因状态机已约束，但初学者易逻辑断裂）。 ✅ 扩展性：该算法天然支持只读迭代器（如 C++ InputIterator）、流式输入（streaming data），只需维护当前和前一个值，空间 O(1)。 ✅ 工程实践：在 Java 中可直接调用 Arrays.stream(arr).sorted().equals(Arrays.stream(arr))，但这是 O(n log n) 时间 + O(n) 空间，仅用于测试，不可用于面试或生产高频调用。 - 附：C++ 实现（体现底层细节） bool isMonotonic(const vector& arr) { int n = arr.size(); if (n <= 2) return true; int direction = 0; // 0: unknown, 1: ascending, -1: descending for (int i = 0; i < n - 1; ++i) { if (arr[i] < arr[i+1]) { if (direction == -1) return false; direction = 1; } else if (arr[i] > arr[i+1]) { if (direction == 1) return false; direction = -1; } } return true; }

全站热榜

创作者周榜