Leetcode 896. 单调数列

Posted on In ,

题目描述

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

如果对于所有 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

解答

这题不能只看任意临近的三个数字有没有单调，因为如果连续三个数字相同并不破坏单调，或是在对子的左右单调性不同。 所以要全局来看每个微分值的符号是否相同。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        if (nums.front()<nums.back()){
            for (int i=0;i<=nums.size()-2;i++){
                if (nums[i]>nums[i+1])
                    return false;
            }
        }
        else{
            for (int i=nums.size()-1;i>=1;i--){
                if (nums[i]>nums[i-1])
                    return false;
            }
        }
        return true;
    }
};

Complexity

  • Time: \(O(n)\)
  • Space: \(O(1)\)