题目：单调数列

  • 如果数组是单调递增或单调递减的，那么它是单调的。
  • 如果对于所有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. 1 <= A.length <= 50000
  2. -100000 <= A[i] <= 100000

来源：力扣（LeetCode）第896题

链接：https://leetcode-cn.com/problems/monotonic-array

分析：

  • 通过大于为1，等于为0，小于为-1判断列表是否单调。
  • 如果一个数中既出现了1，也出现了-1，那么它不是单调数组。
  • 有一点要注意，Python2中自带cmp的函数，可以直接判断，而Python3中将cmp函数移除了，所以Python3中需要自己写一个cmp函数，而Python2中不用。

代码：

  • Python

    class Solution:
def isMonotonic(self, A: List[int]) -> bool:
    compare = set()
    def cmp(i, j):  # 用于判断的集合
        if i > j:
            return 1
        elif i < j:
            return -1
        else:
            return 0
    for i in range(len(A) - 1):
        compare.add(cmp(A[i], A[i+1]))
        if 1 in compare and -1 in compare:
            return False
    return True

  • Java

    class Solution {
public boolean isMonotonic(int[] A) {
    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < A.length - 1; i++) {
        int num = Integer.compare(A[i], A[i+1]);
        set.add(num);
        if (set.contains(1) && set.contains(-1)) {
            return false;
        }
    }
    return true;
}
}

复杂度分析：

  • 时间复杂度：O(n) n为数组的长度。
  • 空间复杂度：O(1)