单调序列

发表于 | 分类于 | 浏览 次
  1. 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.

Example 1:

1
2
Input: [1,2,2,3]
Output: true

Example 2:

1
2
Input: [6,5,4,4]
Output: true

Example 3:

1
2
Input: [1,3,2]
Output: false

Example 4:

1
2
Input: [1,2,4,5]
Output: true

Example 5:

1
2
Input: [1,1,1]
Output: true

Note:

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

方法一：两次遍历

第一遍检查序列是否是递增序列；第二遍检查序列是否是递减序列．

方法二：一次遍历

遍历一次，依次查看相邻两对数的变化趋势是否相等，若相反，则说明不是单调序列．

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:
    bool isMonotonic(vector<int>& A) {
        int store = 0;
        for(int i=0;i<A.size()-1;++i){
            int c = compare(A[i], A[i+1]);
            if(c!=0){ // A[i] != A[i+1]
                //  A[i] != A[i+1] and  A[i-1] != A[i] 
                // then A[i] > A[i+1] and A[i-1] > A[i]
                // or A[i] < A[i+1] and A[i-1] < A[i]
                if(c!= store && store != 0){
                    return false;
                }
                store = c;
            }
        }
        return true;
    }
    int compare(int a, int b){
        if(a == b){
            return 0;
        }
        return a < b ? -1 : 1;
    }
};

方法三：一次遍历(变种)

如果一个序列是单调递增的，那么不会出现相邻两个数递减的趋势，同理，若一个序列是单调递减的，那么不会出现递增的趋势．
如果在一个序列中同时出现了递增和递减的趋势，说明该序列不是单调序列．

1
2