LC 896. 单调数列

题目描述

这是 LeetCode 上的 896. 单调数列 ，难度为 简单。

如果数组是单调递增或单调递减的，那么它是单调的。

如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。

当给定的数组 A 是单调数组时返回 true，否则返回 false。

示例 1：

1
2
输入：[1,2,2,3]
输出：true

示例 2：
1
2
输入：[6,5,4,4]
输出：true

示例 3：
1
2
输入：[1,3,2]
输出：false

示例 4：
1
2
输入：[1,2,4,5]
输出：true

示例 5：
1
2
输入：[1,1,1]
输出：true

提示：

  • 1 <= A.length <= 50000
  • -100000 <= A[i] <= 100000

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

image.png

两次遍历，分别检查是否为单调递增和单调递减。

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)$

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

image.png

一次遍历。

同时为了防止扫完整个数组，增加一个提前 return 的逻辑：

1
2
3
4
5
6
7
8
9
10
11
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)

image.png

简单题，大家就看个乐呵 ~

有趣的实验

评论区有位同学提出了一个很有意思的问题：如果数据量很大，大到内存都无法一次完全读入，那么一个循环里两次重复读应该比两次循环要快得多了吧？

我理解 ta 的意思是，每次读取值都算一次 IO 成本的话，一个循环里两次重复读的的成本应该是要小于比两次循环的成本吧？

因此有了以下的测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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.896 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

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

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

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