单调数列

发表于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

LeetCode每日一题，738. Monotonic Array

先看题目描述

69t5gs.png

大意就是给定一个数列 A，让我们判断其是否是单调数列

算法和思路

两次遍历

先遍历一次 A数组构造出差分数组 diff，再遍历 diff 数组找出 diff 数组中元素的最大值和最小值，判断其最大值和最小值是否同号即可

一次遍历

遍历一次 A 数组，若 A 数组中既出现 A[i] > A[i - 1] 的元素又出现 A[i] < A[i - 1] 的元素，那么一定不是单调数列，则返回 false，否则返回 true

算法源码

两次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isMonotonic(int[] A) {
        int len = A.length;
        if (len <= 2) {
            return true;
        }
        int[] diff = new int[len - 1];
        for (int i = 0; i < len - 1; i++) {
            diff[i] = A[i + 1] - A[i];
        }
        int max = diff[0];
        int min = diff[0];
        for (int num : diff) {
            max = Math.max(num, max);
            min = Math.min(num, min);
        }
        return max * min >= 0;
    }
}

一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isMonotonic(int[] A) {
        int len = A.length;
        boolean ascend = true;
        boolean desc = true;
        for (int i = 1; i < len; i++) {
            if (A[i] > A[i - 1]) {
                desc = false;
            }
            if (A[i] < A[i - 1]) {
                ascend = false;
            }
        }
        return ascend || desc;
    }
}

下面是看运行效率比较优秀的代码看到的方法，大致思路就是比较 A 数组中的第一个元素 A[0] 和最后一个元素 A[len - 1]，若 A[0] < A[len - 1]，那么若 A 是个单调数列，则其一定是个单调递增数列，不能出现 A[i] < A[i - 1] 的元素；若 A[0] > A[len - 1]，那么若 A 是个单调数列，则其一定是个单调递减数列，不能出现 A[i] > A[i - 1] 的元素；若 A[0] 与 A[len - 1] 相等，那么若 A 是个单调数列，则其中所有元素必定相等，不能出现不相等的元素

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 {
    public boolean isMonotonic(int[] A) {
        int len = A.length;
        if (A[0] < A[len - 1]) {
            for (int i = 1; i < len; i++) {
                if (A[i] < A[i - 1]) {
                    return false;
                }
            }
        } else if (A[0] > A[len - 1]) {
            for (int i = 1; i < len; i++) {
                if (A[i] > A[i - 1]) {
                    return false;
                }
            }
        } else {
            for (int i = 1; i < len; i++) {
                if (A[i] != A[i - 1]) {
                    return false;
                }
            }
        }
        return true;
    }
}