896.monotonic array
896.Monotonic Array
如果数组是单调递增或单调递减的,那么它是单调的。 如果对于所有 i <= j,A[i] <= A[j],那么数组 A 是单调递增的。 如果对于所有 i <= j,A[i]> = A[j],那么数组 A 是单调递减的。 当给定的数组 A 是单调数组时返回 true,否则返回 false。
1
示例 1:
2
3
输入:[1,2,2,3]
4
输出:true
5
示例 2:
6
7
输入:[6,5,4,4]
8
输出:true
9
示例 3:
10
11
输入:[1,3,2]
12
输出:false
13
示例 4:
14
15
输入:[1,2,4,5]
16
输出:true
17
示例 5:
18
19
输入:[1,1,1]
20
输出:true
21
22
23
提示:
24
25
1 <= A.length <= 50000
26
-100000 <= A[i] <= 100000
Copied!
方法: 题目比较简单,唯一的难点在于如何改进时间。最初想法如下,先从第一个开始判断,如果大于的往后判断,碰到小于的就返回false。小于也是一样,等于的话删掉第一个元素,递归调用。
1
class Solution {
2
public:
3
bool isMonotonic(vector<int>& A) {
4
int n=A.size();
5
if(n==1)
6
return true;
7
if(A[0]>A[1] )
8
{
9
int i=2;
10
while(i<n)
11
{
12
if(A[i-1]<A[i])
13
return false;
14
i++;
15
}
16
return true;
17
}
18
if(A[0] < A[1])
19
{
20
int i=2;
21
while(i<n)
22
{
23
if(A[i-1]>A[i])
24
return false;
25
i++;
26
}
27
return true;
28
}
29
if(A[0]==A[1])
30
{
31
A.erase(A.begin());
32
return isMonotonic(A);
33
}
34
35
}
36
};
Copied!
更短时间的例子如下,通过两个计数器遍历一遍向量即可。
1
class Solution {
2
public:
3
bool isMonotonic(vector<int>& A) {
4
int length=A.size();
5
int inc=0,dec=0;
6
for(int i=0;i<length-1;++i)
7
{
8
if (A[i]>=A[i+1])
9
dec++;
10
if (A[i]<=A[i+1])
11
inc++;
12
}
13
if (inc==length-1 || dec==length-1)
14
return true;
15
else
16
return false;
17
}
18
};
Copied!
Copy link