LeetCode 896 - Monotonic Array

https://leetcode.com/articles/monotonic-array/

An array is monotonic if it is either monotone increasing or monotone decreasing.

An array A is monotone increasing if for all i <= j, A[i] <= A[j].  An array A is monotone decreasing if for all i <= j, A[i] >= A[j].

Return true if and only if the given array A is monotonic.

To perform this check in one pass, we want to handle a stream of comparisons from $\{-1, 0, 1\}$, corresponding to <, ==, or >. For example, with the array [1, 2, 2, 3, 0], we will see the stream (-1, 0, -1, 1).

Algorithm

Keep track of store, equal to the first non-zero comparison seen (if it exists.) If we see the opposite comparison, the answer is False.

Otherwise, every comparison was (necessarily) in the set $\{-1, 0\}$, or every comparison was in the set $\{0, 1\}$, and therefore the array is monotonic.

    public boolean isMonotonic(int[] A) {
        int store = 0;
        for (int i = 0; i < A.length - 1; ++i) {
            int c = Integer.compare(A[i], A[i+1]);
            if (c != 0) {
                if (c != store && store != 0)
                    return false;
                store = c;
            }
        }

        return true;
    }

    public boolean isMonotonic(int[] A) {
        boolean increasing = true;
        boolean decreasing = true;
        for (int i = 0; i < A.length - 1; ++i) {
            if (A[i] > A[i+1])
                increasing = false;
            if (A[i] < A[i+1])
                decreasing = false;
        }

        return increasing || decreasing;
    }

    public boolean isMonotonic(int[] A) {

        return increasing(A) || decreasing(A);

    }

    public boolean increasing(int[] A) {

        for (int i = 0; i < A.length - 1; ++i)

            if (A[i] > A[i+1]) return false;

        return true;

    }

    public boolean decreasing(int[] A) {

        for (int i = 0; i < A.length - 1; ++i)

            if (A[i] < A[i+1]) return false;

        return true;

    }

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/896_Monotonic_Array.java

    public boolean isMonotonic(int[] A) {
        boolean inc = true, dec = true;
        for (int i = 1; i < A.length; i ++) {
            inc &= A[i - 1] <= A[i];
            dec &= A[i - 1] >= A[i];
            if (!inc && !dec) return false;
        }
        return true;
    }

followup是

1. 问了了我的做法的time & space complexity

2. 如果这个vector特别⼤大（entries⾮非常多）我们不不能⼀一次性把它pass进

去，应该怎么办？给了了⼀一个helper function叫 int nextNum();