点击 这里 可以查看更多算法面试相关内容~
题目描述
这是 LeetCode 上的896. 单调数列，难度为 Easy。
如果数组是单调递增或单调递减的，那么它是单调的。
- 如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。
- 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。
当给定的数组 A 是单调数组时返回 true，否则返回 false。
示例 1：
输入：[1,2,2,3] 输出：true 复制代码
示例 2：
输入：[6,5,4,4] 输出：true 复制代码
示例 3：
输入：[1,3,2] 输出：false 复制代码
示例 4：
输入：[1,2,4,5] 输出：true 复制代码
示例 5：
输入：[1,1,1] 输出：true 复制代码
提示：
- 1 <= A.length <= 50000
- -100000 <= A[i] <= 100000
朴素解法（所谓的两次遍历）
两次遍历，分别检查是否为单调递增和单调递减。
class Solution { public boolean isMonotonic(int[] a) { return check(a, true) || check(a, false); } boolean check(int[] a, boolean flag) { for (int i = 0; i < a.length - 1; i++) { if (flag) { if (a[i] > a[i + 1]) return false; } else { if (a[i] < a[i + 1]) return false; } } return true; } } 复制代码
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
朴素解法（所谓的一次遍历）
一次遍历。
同时为了防止扫完整个数组，增加一个提前 return 的逻辑：
class Solution { public boolean isMonotonic(int[] a) { boolean up = true, down = true; for (int i = 0; i < a.length - 1; i++) { if (a[i] > a[i + 1]) up = false; if (a[i] < a[i + 1]) down = false; if (!up && !down) return false; } return up || down; } } 复制代码
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
总结
事实上，上述两种解法其实并不应该区分为「一次遍历」与「两次遍历」。
我们应该用「对数组的访问次数」来定义遍历多少次，而不是「利用 for 循环的个数」来定义。上述无论那种方法，对数组访问次数都是一样的。
而在不对解法二进行剪枝的情况下，要比解法一慢。主要是因为解法一明确了是「递增」还是「递减」之后，在循环内部做了剪枝。
当我们对解法二进行同样的内部剪枝之后，其实和解法一应该是类似的。
前三次提交是保留 if (!up && !down) return false; 的提交 (1 ms)
后三次提交是不保留 if (!up && !down) return false; 的提交记录 (2 ms)
有趣的实验
在 LeetCode 上有位同学提出了一个很有意思的问题：如果数据量很大，大到内存都无法一次完全读入，那么一个循环里两次重复读应该比两次循环要快得多了吧？
我理解 ta 的意思是，每次读取值都算一次 IO 成本的话，一个循环里两次重复读的的成本应该是要小于比两次循环的成本吧？
因此有了以下的测试代码：
class Solution { // 统计「二次循环」的访问次数 int cnt; public boolean isMonotonic(int[] a) { cnt = 0; // 这里不直接写成「短路与」进行返回，确保两个循环都会被执行 boolean t = check(a, true), u = check(a, false); System.out.println(cnt); return t || u; } boolean check(int[] a, boolean flag) { for (int i = 0; i < a.length - 1; i++) { if (flag) { if (getVal(a, i) > getVal(a, i + 1)) return false; } else { if (getVal(a, i) < getVal(a, i + 1)) return false; } } return true; } int getVal(int[] a, int idx) { cnt++; return a[idx]; } } 复制代码
对于样例数据的输出：8 8 6 8 8
class Solution { // 统计「一次循环」的访问次数 int cnt; public boolean isMonotonic(int[] a) { cnt = 0; boolean up = true, down = true; for (int i = 0; i < a.length - 1; i++) { if (getVal(a, i) > getVal(a, i + 1)) up = false; if (getVal(a, i) < getVal(a, i + 1)) down = false; if (!up && !down) break; } System.out.println(cnt); return up || down; } int getVal(int[] a, int idx) { cnt++; return a[idx]; } } 复制代码
对于样例数据的输出：12 12 8 12 8
在样例数据中已经覆盖了递增、递减、常规数组、等值数组几种情况了，因此这个输出结果对比 我认为是具有普遍性的。存疑的同学可以写一个随机数组生成器去测试一下 ~
结论：二次循环的剪枝效果应该是要比一次循环要更好点（更加直接）。如果还有人坚持「所谓的一次循环」要优于「所谓的二次循环」，实验代码就是最好的证明。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
