896.单调数列

• 难度：简单

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

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

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

示例

示例1：

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

示例2：

输入：[6,5,4,4]
输出：true

示例3：

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

示例4：

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

示例5：

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

说明

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

思路

• 标志位大法
  1. 递增标志位为true，递减标志位为true
  2. 遍历数组
     • 若前数大于后数，把递减标记位置为false
     • 若前数小于后数，把递增标记位置为false
     • 若前数小于后数，所有标志位都保持
  3. 递增标志位 || 递减标志位 得到 是否 单调数列

• STL外挂
  1. 调用两次STL算法库中的is_sorted()函数
     • 第一次检测其是否单调递增
     • 第二次检测其是否单调递减

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//标志位打法好呀ε=ε=ε=┏(゜ロ゜;)┛
bool isMonotonic(vector<int>& A) {
    bool zeng = true;
    bool jian = true;
    
    for(int i = 0;i<A.size()-1;i++){
        if(A[i] > A[i+1])
            jian = false;
        
        if(A[i] < A[i+1])
            zeng = false;
    }
    
    return zeng || jian;
}

//迫不得已，我们不首先使用外挂
bool isMonotonic(vector<int>& A) {
    return is_sorted(A.begin(),A.end()) || is_sorted(A.rbegin(),A.rend());
}