j

jaryue

V1

2023/05/24阅读:8主题:默认主题

leetcode 896. 单调数列

leetcode 896. 单调数列


题目描述

  1. 单调数列

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

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

首先,判断数组的长度 n 是否小于等于 2,如果是,则数组一定是单调的,直接返回 true。

声明两个布尔变量 isIncreasing 和 isDecreasing,初始化为 true。 遍历数组 nums,从第二个元素开始比较。

如果当前元素 nums[i] 大于前一个元素 nums[i-1],则说明数组是单调递增的,将 isIncreasing 置为 false。

如果当前元素 nums[i] 小于前一个元素 nums[i-1],则说明数组是单调递减的,将 isDecreasing 置为 false。

在比较的过程中,如果既出现了递增又出现了递减,说明数组不是单调的,直接返回 false。

遍历完成后,如果没有出现递增和递减的情况,说明数组既不是单调递增也不是单调递减,返回 true。

  • 时间复杂度(O(n))
  • 空间复杂度(O(1))

执行结果

法1

我们首先将 increasing 和 decreasing 初始化为 true,表示假设数组是递增和递减的。

然后在遍历数组时,如果出现 nums[i] > nums[i-1],即当前元素大于前一个元素,就将 decreasing 置为 false,表示数组不是递减的;如果出现 nums[i] < nums[i-1],即当前元素小于前一个元素,就将 increasing 置为 false,表示数组不是递增的。

这样,在遍历完成后,如果 increasing 或 decreasing 有一个为 true,则说明数组是单调的。

func isMonotonic(nums []int) bool {
    n := len(nums)
    if n <= 2 {
        return true
    }

    increasing := true
    decreasing := true

    for i := 1; i < n; i++ {
        if nums[i] > nums[i-1] {
            decreasing = false
        } else if nums[i] < nums[i-1] {
            increasing = false
        }
    }

    return increasing || decreasing
}

执行结果: 通过 显示详情 查看示例代码 添加备注

执行用时: 128 ms , 在所有 Go 提交中击败了 68.69% 的用户 内存消耗: 8.2 MB , 在所有 Go 提交中击败了 75.76% 的用户 通过测试用例: 371 / 371 炫耀一下:



分类:

后端

标签:

后端

作者介绍

j
jaryue
V1