【LeetCode】896. 单调数列

发表于 更新于 分类于 Valine：
本文字数： 106 阅读时长 ≈ 1 分钟

896. 单调数列

思路

  1. 遍历判断
  2. 逻辑运算
    • || 如果两个操作数中有任意一个非零，则条件为真

代码

精简版 两次遍历数组，逻辑运算 64ms
1
2
3
4
5
6
class Solution {
public:
    bool isMonotonic(vector<int> &A) {
        return is_sorted(A.begin(), A.end()) || is_sorted(A.rbegin(), A.rend());
    }
};
一次遍历，逻辑运算 64ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isMonotonic(vector<int> &A) {
        bool inc = true, dec = true;
        int n = A.size();
        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;
    }
};
一次遍历，无逻辑运算 88ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        int size=A.size();
        if(size==1)
            return true;
        int flag=0;
        int last=0;
        for(int i=0;i<size-1;i++)
        {
            flag=A[i]-A[i+1];
            //记录首次出现变化的时候，是递增还是递减
            if(flag>0&&last==0) last=-1;
            if(flag<0&&last==0) last=1;
            //出现变化与首次变化不同，则不是单调序列
            if(flag>0&&last==1) return false;
            if(flag<0&&last==-1) return false;
        }
        return true;
    }
};
一次遍历，无逻辑运算，优化版 72ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        int size=A.size();
        if(size==1)
            return true;
        int flag=0;
        int last=0;
        for(int i=0;i<size-1;i++)
        {
            flag=A[i]-A[i+1];
            //记录首次出现变化的时候，是递增还是递减
            if(last==0)
            {
                if(flag>0) last=-1;
                if(flag<0) last=1;
            }
            //出现变化与首次变化不同，则不是单调序列
            if(flag>0&&last==1) return false;
            if(flag<0&&last==-1) return false;
        }
        return true;
    }
};