leetcode-896-单调数列
leetcode-896-单调数列
chenjx85
发布于 2018-09-29 15:23:24
发布于 2018-09-29 15:23:24
题目描述：
如果数组是单调递增或单调递减的，那么它是单调的。
如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[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 <= A.length <= 50000-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。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-09-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录