Question

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)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

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

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

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

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

function isMonotonic(nums: number[]): boolean {
  let [asc, desc] = [false, false];
  for (let i = 1; i < nums.length; ++i) {
    if (nums[i - 1] < nums[i]) {
      asc = true;
    } else if (nums[i - 1] > nums[i]) {
      desc = true;
    }
    if (asc && desc) {
      return false;
    }
  }
  return true;
}

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

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