896. 单调数列

Posted on | In
Words count in article: 498 | Reading time ≈ 2

题目

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

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

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

示例1：

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

示例2：

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

示例3：

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

示例4：

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

示例5：

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

提示：

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

解答

解法一

遍历两次数组，分别判断是否递增或者递减。时间复杂度O(2 * n)

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean isMonotonic(int[] A) {
	boolean isAsc = isAsc(A);
	boolean isDesc = isDesc(A);
	return isAsc || isDesc;
}

private boolean isAsc(int[] A) {
	for (int i = 0;i < A.length - 1;i++) {
		if (A[i + 1] < A[i]) {
			return false;
		}
	}
	return true;
}

private boolean isDesc(int[] A) {
	for (int i = 0;i < A.length - 1;i++) {
		if (A[i + 1] > A[i]) {
			return false;
		}
	}
	return true;
}

解法二

遍历两次感觉有点多余了，那么是不是可以把遍历次数限制在一次呢。其实是可以的。我们可以在一次循环中判断数列是否是一个单调数列。

定义两个变量isAcs，isDesc，初始化为true。然后遍历数列，只要在遍历的过程中，发现A[i] < A[i + 1]， 那么数列就不是递减的，isDesc就是false，反之，如果A[i] > A[i + 1]，数列就不是递增的，isAsc就是false。最后的结果，取isAsc || isDesc即可，两者只要一个为true，就是单调序列。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isMonotonic(int[] A) {
		boolean isAsc = true;
		boolean isDesc = true;
		
		for (int i = 0;i < A.length - 1;i++) {
			if (A[i] < A[i + 1]) {
				isDesc = false;
			}
			
			if (A[i] > A[i + 1]) {
				isAsc = false;
			}
		}
		
		return isAsc || isDesc;
	}
0%