README.md

896. 单调数列

English Version

题目描述

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

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

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

 

示例 1：

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

示例 2：

输入：nums = [6,5,4,4]
输出：true

示例 3：

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

 

提示：

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105

解法

方法一：一次遍历

遍历数组，如果出现递增或递减的情况，记录下来。判断是否出现过递增和递减的情况，如果都出现过，说明不是单调数组，返回 false。

否则遍历结束，说明是单调数组，返回 true。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组长度。

Python3

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        isIncr = isDecr = False
        for i, v in enumerate(nums[1:]):
            if v < nums[i]:
                isIncr = True
            elif v > nums[i]:
                isDecr = True
            if isIncr and isDecr:
                return False
        return True

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        incr = all(a <= b for a, b in pairwise(nums))
        decr = all(a >= b for a, b in pairwise(nums))
        return incr or decr

Java

class Solution {
    public boolean isMonotonic(int[] nums) {
        boolean isIncr = false, isDecr = false;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] < nums[i - 1]) {
                isIncr = true;
            } else if (nums[i] > nums[i - 1]) {
                isDecr = true;
            }
            if (isIncr && isDecr) {
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        bool isIncr = false;
        bool isDecr = false;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < nums[i - 1]) isIncr = true;
            if (nums[i] > nums[i - 1]) isDecr = true;
            if (isIncr && isDecr) return false;
        }
        return true;
    }
};

Go

func isMonotonic(nums []int) bool {
	isIncr, isDecr := false, false
	for i, v := range nums[1:] {
		if v < nums[i] {
			isIncr = true
		} else if v > nums[i] {
			isDecr = true
		}
		if isIncr && isDecr {
			return false
		}
	}
	return true
}

JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isMonotonic = function (nums) {
    let isIncr = false;
    let isDecr = false;
    for (let i = 1; i < nums.length; ++i) {
        if (nums[i] < nums[i - 1]) {
            isIncr = true;
        }
        if (nums[i] > nums[i - 1]) {
            isDecr = true;
        }
        if (isIncr && isDecr) {
            return false;
        }
    }
    return true;
};

TypeScript

function isMonotonic(nums: number[]): boolean {
    const n = nums.length;
    let isOrder = false;
    let isDecs = false;
    for (let i = 1; i < n; i++) {
        const pre = nums[i - 1];
        const cur = nums[i];
        if (pre < cur) {
            isOrder = true;
        } else if (pre > cur) {
            isDecs = true;
        }
        if (isOrder && isDecs) {
            return false;
        }
    }
    return true;
}

Rust

impl Solution {
    pub fn is_monotonic(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut is_order = false;
        let mut is_decs = false;
        for i in 1..n {
            let pre = nums[i - 1];
            let cur = nums[i];
            if pre < cur {
                is_order = true;
            } else if pre > cur {
                is_decs = true;
            }
            if is_order && is_decs {
                return false;
            }
        }
        true
    }
}

...