判断数组是否单调增/减

思路一：两次遍历

如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。
当给定的数组 A 是单调数组时返回 true，否则返回 false。

分别遍历是否是单调增或单调减
bool isSorted(int* A, int ASize, bool increasing) {
if (increasing) {
for (int i = 0; i < ASize - 1; ++i) {
if (A[i] > A[i + 1]) {
return false;
}
}
} else {
for (int i = 0; i < ASize - 1; ++i) {
if (A[i] < A[i + 1]) {
return false;
}
}
}
return true;
}

bool isMonotonic(int* A, int ASize) {
    return isSorted(A, ASize, true) || isSorted(A, ASize, false);
}

思路二：一次遍历

遍历数组A，若既遇到了A[i] > A[i+1]，也遇到了A[i]<A[i+1]，则说明：既不是单调递减的，也不是单调递增的

写法一

bool isMonotonic(int* A, int ASize) {
    bool inc = true, dec = true;
    int n = ASize;
    for (int i = 0; i < n - 1; ++i) {
        if (A[i] > A[i + 1]) {
            inc = false;
        }
        if (A[i] < A[i + 1]) {
            dec = false;
        }
    }
    return inc || dec;
}

写法二

bool isMonotonic(int* A, int ASize){
    int a = 0, b = 0;
    for(int i = 0; i < ASize - 1; i++){
        if(A[i] <= A[i+1]){
            a++;
        }
        if(A[i] >= A[i+1]) {
            b++;
        }
    }
    if(a == ASize - 1 || b == ASize - 1){
        return true;
    }
    else{
        return false;
    }
}

总结

两种思路的时间复杂度都是：O(n)