今天看了道算法题，
判断一个数组是否为单调数组，是返回 true，不是返回 false。
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
|
思考
单调即数组后一项都比前一项大，或都比前一项小
重点是 每一项 和 比较
- 要能遍历每一项，需要循环数组
- 比较，这个就有文章了
怎么比较
因为有两种情况
因此最简单的是两个if判断一下，于是就有
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
const isMonotonic = function(list) {
return incMon(list) || decMon(list)
};
const incMon = function(list) {
let isMon = false;
for(let i = 0; i<list.length-1; i+=1){
if(list[i]-list[i+1] > 0) isMon = true
}
return isMon;
};
const decMon = function(list) {
let isMon = false;
for(let i = 0; i<list.length-1; i+=1){
if(list[i]-list[i+1] < 0) isMon = true
}
return isMon;
};
|
emmm，上面这段是有bug的，因为就算循环了，但判断条件只要有一项满足即为true，因此无法检测类似[1,3,2]这种数组，怎么办？
问题在哪呢？
上面两个incMon和decMon的前提假设是传入的数组不是单调数组，如果假设传入是单调，只要判断出有一项不符合，就返回false，那应该就不会有问题了。
于是，改为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
const isMonotonic = function(list) {
return incMon(list) || decMon(list)
};
const incMon = function(list) {
let isMon = true;
for(let i = 0; i<list.length-1; i+=1){
if(list[i]-list[i+1] < 0) isMon = false;
}
return isMon;
};
const decMon = function(list) {
let isMon = true;
for(let i = 0; i<list.length-1; i+=1){
if(list[i]-list[i+1] > 0) isMon = false;
}
return isMon;
};
|
嗯，
条件判断应该尽量判断特殊情况。
再看看刚才代码，感觉两个增减判断函数里for循环功能类似，仅判断条件不一样，第六感告诉我这还有优化空间。
心中默念：
写代码的目的是为了有一天能不写代码。
来，继续。
优化
非单调的情况是
- 递增的出现
list[i]-list[i+1] > 0
- 递减的出现
list[i]-list[i+1] < 0
然后可以有
1
2
3
4
5
6
7
8
9
10
11
12
13
|
const isMonotonic = function(list) {
let incFlag = true;
let decFlag = true;
for(let i = 0, i<list.length-1,i+=1){
if(list[i]-list[i+1]>0) incFlag = false;
if(list[i]-list[i+1]<0) decFlag = false;
}
return incFlag || decFlag
}
|
嗯，看着优雅多了
ShowCase
咦，当数组只有一个数的时候必定是单调函数，就不用再费事去循环了！
再优化下，加个判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
const isMonotonic = function(list) {
+ if(list.length <= 1) return true;
let incFlag = true;
let decFlag = true;
for(let i = 0, i<list.length-1,i+=1){
if(list[i]-list[i+1]>0) incFlag = false;
if(list[i]-list[i+1]<0) decFlag = false;
}
return incFlag || decFlag
}
|
嗯，这回应该不错了。
还有别的方法嘛？
有的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| const isMonotonic = function(A) {
let flag = 0;
if (A.length <= 1) return true;
for (let i = 1; i < A.length; i++) {
if (A[i] > A[i - 1]) {
if (flag === 2) return false;
flag = 1;
} else if (A[i] < A[i - 1]) {
if (flag === 1) return false;
flag = 2;
}
}
return true;
};
|
本文完。