题目

标题和出处

标题：单调数列

出处：896. 单调数列

难度

2 级

题目描述

要求

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

如果对于所有 $\text{i}\le \text{j}$，$\text{nums[i]}\le \text{nums[j]}$，那么数组 $\text{nums}$ 是单调递增的。如果对于所有 $\text{i}\le \text{j}$，$\text{nums[i]}\ge \text{nums[j]}$，那么数组 $\text{nums}$ 是单调递减的。

当给定的数组 $\text{nums}$ 是单调数组时返回 $\text{true}$，否则返回 $\text{false}$。

示例

示例 1：

输入：$\text{nums = [1,2,2,3]}$
输出：$\text{true}$

示例 2：

输入：$\text{nums = [6,5,4,4]}$
输出：$\text{true}$

示例 3：

输入：$\text{nums = [1,3,2]}$
输出：$\text{false}$

示例 4：

输入：$\text{nums = [1,2,4,5]}$
输出：$\text{true}$

示例 5：

输入：$\text{nums = [1,1,1]}$
输出：$\text{true}$

数据范围

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{5}}$
• ${\text{-10}}^{\text{5}}\le \text{nums[i]}\le {\text{10}}^{\text{5}}$

解法

思路和算法

这道题目要求判断给定的整数数组 $\text{nums}$ 是否单调。假设数组 $\text{nums}$ 单调递增，对任意 $i<j$ 都有 $\text{nums}[i]\le \text{nums}[j]$，当 $j-i>1$ 时，对任意 $i<k<j$ 都有 $\text{nums}[i]\le \text{nums}[k]\le \text{nums}[j]$。显然，当 $i<k<j$ 时，如果下标对 $(i,k)$ 和 $(k,j)$ 都满足单调递增关系，则下标对 $(i,j)$ 也一定满足单调递增关系。对于单调递减的情况同理。因此，只需要计算数组 $\text{nums}$ 的每一对相邻元素之间的大小关系即可。

当数组 $\text{nums}$ 单调递增时，对于任意 $i\ge 0$ 都有 $\text{nums}[i]\le \text{nums}[i+1]$，即不可能出现 $\text{nums}[i]>\text{nums}[i+1]$。当数组 $\text{nums}$ 单调递减时，不可能出现 $\text{nums}[i]<\text{nums}[i+1]$。由于相邻元素相等的情况在单调递增数组和单调递减数组中都可能出现，因此只需要考虑相邻元素不相等的情况。

具体而言，如果数组 $\text{nums}$ 的每一对相邻元素的差（指后项减前项）都大于等于 $0$，则数组 $\text{nums}$ 单调递增，如果数组 $\text{nums}$ 的每一对相邻元素的差都小于等于 $0$，则数组 $\text{nums}$ 单调递减，这两种情况下，数组 $\text{nums}$ 都是单调的。如果数组 $\text{nums}$ 相邻元素的差既有大于 $0$ 的情况也有小于 $0$ 的情况，则数组 $\text{nums}$ 不单调。

代码

class Solution {
    public boolean isMonotonic(int[] nums) {
        int length = nums.length;
        int prevDifference = 0;
        for (int i = 1; i < length; i++) {
            int difference = nums[i] - nums[i - 1];
            if (prevDifference > 0 && difference < 0 || prevDifference < 0 && difference > 0) {
                return false;
            }
            if (difference != 0) {
                prevDifference = difference;
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。需要遍历数组 $\text{nums}$ 一次，判断每一对相邻元素的大小关系。

• 空间复杂度：$O(1)$。

最后

以上就是娇气荷花为你收集整理的数组题目：单调数列题目解法的全部内容，希望文章能够帮你解决数组题目：单调数列题目解法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。