leetcode-896-单调数列

题目描述:

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

如果对于所有 i <= jA[i] <= A[j],那么数组 A 是单调递增的。 如果对于所有 i <= jA[i]> = A[j],那么数组 A 是单调递减的。

当给定的数组 A 是单调数组时返回 true,否则返回 false

示例 1:

输入:[1,2,2,3]
输出:true

示例 2:

输入:[6,5,4,4]
输出:true

示例 3:

输入:[1,3,2]
输出:false

示例 4:

输入:[1,2,4,5]
输出:true

示例 5:

输入:[1,1,1]
输出:true

提示:

  1. 1 <= A.length <= 50000
  2. -100000 <= A[i] <= 100000

要完成的函数:

bool isMonotonic(vector<int>& A) 

说明:

1、这道题给定一个vector,长度大于等于1,存储的是int类型的数据,要求判断这个vector是不是单调的(可以等于)。

如果是单调的,返回true,如果不是,返回false。

2、这道题不会很难,把一些边界情况考虑一下,也就差不多能解决了~

首先如果vector只有一个元素或者两个元素,那么必定是单调的。(长度已经规定>=1)

接着找到第一个跟前面元素不相等的元素,我们通过它来判断如果是单调数组,是单调上升的,还是单调下降的。(如果没有找到这个元素,那么说明整个vector的元素都是完全相等的,那么返回true)

接着就是在这个元素后面继续遍历了,发现与前面规律不一致的就返回false。

如果到了末尾都没有返回false,那么返回true。

代码如下:(附详解)

    bool isMonotonic(vector<int>& A) 
    {
        if(A.size()==1||A.size()==2)return true;//边界情况,这里注意后面是||A.size()==2而不是||2
        int i=1;
        while(i<A.size())//找到第一个跟前面元素不一样的元素
        {
            if(A[i]!=A[i-1])
                break;
            i++;
        }
        if(i==A.size())return true;//如果到了末尾都没有找到,那么这是一个元素完全相等的vector,返回true
        if(A[i]>A[i-1])//如果这个元素大于前一个,那么应该是单调上升的
        {
            i++;
            while(i<A.size())//一直比较
            {
                if(A[i]<A[i-1])//发现异常情况,小于前一个元素
                    return false;//返回false
                i++;
            }
            return true;//一直没有返回false,那么返回true
        }
        else//单调下降的情况,同理
        {
            i++;
            while(i<A.size())
            {
                if(A[i]>A[i-1])
                    return false;
                i++;
            }
            return true;
        }
    }

上述代码实测56ms,beats 98.71% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

hust 1607 Triangles(经典好题)

题意:给出一定的点,然后再给出哪些点相连,问最后这些相连点的组成多少个三角形,hash的应用 分析:转载牛人的思想 题意:给一些点的坐标和里面的点构成的一些线段...

30180
来自专栏木子昭的博客

机器学习三剑客之NumpyNumpy计算(重要)

NumPy是Python语言的一个扩充程序库。支持高级大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库。Numpy内部解除了Python的PI...

37460
来自专栏mathor

科学计算库Numpy

 genfromtxt函数里穿了三个参数,分别是 要打开的文档名称,分隔符,以什么类型存储  打印结果:

12140
来自专栏数据结构与算法

10:单词排序

10:单词排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入一行单词序列,相邻单词之间由1个或多个空格间隔,请按照...

40770
来自专栏ACM算法日常

将树围起来(几何凸包)- HDU 1392

在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。如下图所示。计算凸包也就是求得外围(蓝线上)的那些点。

10120
来自专栏程序生活

连续子数组的最大和

题目1 连续子数组的最大和 描述: 输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度...

31450
来自专栏深度学习之tensorflow实战篇

python 中numpy基本方法总结可以类推tensorflow

一、数组方法 创建数组:arange()创建一维数组;array()创建一维或多维数组,其参数是类似于数组的对象,如列表等 反过来转换则可以使用numpy.n...

62150
来自专栏武培轩的专栏

剑指Offer-旋转数组的最小数字

package Array; /** * 旋转数组的最小数字 * 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 * 输入一个非递减...

33750
来自专栏chenjx85的技术专栏

leetcode-74-搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

28510
来自专栏前端新视界

使用 JS 输出螺旋矩阵

这是我曾经遇到过的面试题,在 LeetCode 上找到了题目的原型,难度中等。题目描述如下:

13620

扫码关注云+社区

领取腾讯云代金券