题目描述

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

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

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

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