「两次遍历」要比「一次遍历」要慢 ... 为啥呀？为啥呀？？

宫水三叶的刷题日记

关注

发布于: 2021 年 03 月 01 日

题目描述

这是 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(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(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 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

发布于: 2021 年 03 月 01 日阅读数: 10

原文链接:【http://xie.infoq.cn/article/3932e15baef7eb780d8bc650b】。文章转载请联系作者。

宫水三叶的刷题日记

关注

算法爱好者，退役 OIer 2020.03.07 加入

公众号「宫水三叶的刷题日记」。每天十分钟，快乐学算法 ~

发布

暂无评论

创作场景

「两次遍历」要比「一次遍历」要慢 ... 为啥呀？为啥呀？？

题目描述

朴素解法（所谓的两次遍历）

朴素解法（所谓的一次遍历）

总结

有趣的实验

最后

宫水三叶的刷题日记

评论