在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的 第51题：非递减序列 的题目解析，具体如下：

题目描述

题目等级：容易
知识点：数组

查看题目：非递减序列
给了n个数(1<=n<=100000)，分别为a1,a2,a3...an(1<=ai<=1000000000)，对于每一个ai，要么不变，要么让它减1，问能否使这个序列变为非递减序列，如果可以输出"YES"，否则输出"NO"。
输入序列中数字的个数n，和n个数，表示每个ai的值
输出一行字符串，如果可以变为非递减序列输出"YES"，否则输出"NO"

示例1
输入：
5
[1,1,2,1,5]
输出：
"YES"

解题方法：

非递减序列的定义为，序列中任意两个相邻的数，后一个数大于等于前面的数。

遍历数组，比较所有相邻的数字，如果发现当前数字大于后一个的数字，则当前数字需要 -1，并做一个标记，表示这个数字已经减过1了，不能再减1了。同时如果一个数字减一之后，这个数字前面的数字如果比这个数字大了，前面太大的数字也需要跟着减一。

每次做-1操作时，都需要检查标记，若发现在 -1 操作之前，数字已经做过标记，表明该数字无法再-1，序列无法变成非递减序列，返回NO。如果照上述操作整个数组都没有问题，则表明序列可以变成非递减序列，返回YES。

时间复杂度：O(n^2)
空间复杂度：O(1)

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：非递减序列