Question

896. Monotonic Array

中文文档

Description

An array is monotonic if it is either monotone increasing or monotone decreasing.

An array nums is monotone increasing if for all i <= j, nums[i] <= nums[j]. An array nums is monotone decreasing if for all i <= j, nums[i] >= nums[j].

Given an integer array nums, return true_ if the given array is monotonic, or _false_ otherwise_.

 

Example 1:

Input: nums = [1,2,2,3]
Output: true

Example 2:

Input: nums = [6,5,4,4]
Output: true

Example 3:

Input: nums = [1,3,2]
Output: false

 

Constraints:

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

Solutions

Solution 1: Single Traversal

We traverse the array, and if an increasing or decreasing situation occurs, we record it. We then check whether both increasing and decreasing situations have occurred. If both have occurred, it means that the array is not monotonic, and we return false.

Otherwise, if we reach the end of the traversal, it means that the array is monotonic, and we return true.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $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;
};