遇到一个非递减序列问题，求解答
遇到一个非递减序列问题，求解答 给了 n 个数 (1<=n<=100000)，分别为a1,a2,a3...an(1<=ai<=1000000000)，对于每一个 ai，要么不变，要么让它减 1，问能否使这个序列变为非递减序列，如果可以输出 "YES"，否则输出 "NO"。输入序列中数字的个数 n，和 n 个数，表示每个 ai 的值输出一行字符串，如果可以变为非递减序列输出 "YES"，否则输出 "NO"输入序列中数字的个数 n，和 n 个数，表示每个 ai 的值输出一行字符串，如果可以变为非递减序列输出 "YES"，否则输出 "NO"
展开
收起
1
条回答
写回答
写回答
-
非递减序列的定义为，序列中任意两个相邻的数，后一个数大于等于前面的数。遍历数组，比较所有相邻的数字，如果发现当前数字大于后一个的数字，则当前数字需要-1，并做一个标记，表示这个数字已经减过1 了，不能再减 1 了。同时如果一个数字减一之后，这个数字前面的数字如果比这个数字大了，前面太大的数字也需要跟着减一。每次做 -1 操作时，都需要检查标记，若发现在-1操作之前，数字已经做过标记，表明该数字无法再-1，序列无法变成非递减序列，返回NO。如果照上述操作整个数组都没有问题，则表明序列可以变成非递减序列，返回 YES。 因此输入：5 [1,1,2,1,5] 输出："YES"
2021-12-23 18:52:18赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
