51.非递减序列 - 图1

题目概述

题目详情(点我)

给了n个数(1<=n<=100000)，分别为a1,a2,a3…an(1<=ai<=1000000000)，对于每一个ai，要么不变，要么让它减1，问能否使这个序列变为非递减序列，如果可以输出”YES”，否则输出”NO”。

输入:
输入序列中数字的个数n，和n个数，表示每个ai的值

输出:
输出一行字符串，如果可以变为非递减序列输出”YES”，否则输出”NO”

题解

解题方法

  • 数的比较

算法知识

  • 数组的遍历

    • 时间复杂度: n
    • 空间复杂度: 1

解题思路

审题

  • int n : 数的个数
  • int[] nums : 存储数的数组

  • 可以对a[i] 进行两种操作

    • +1
    • 不变

题目要求

  • 判断是否为非递减序列 [要求nums[i]小于等于之后的每个数]

思路

  • 根据非递减序列的定义以及可以对a[i]进行的两种操作, 我们可以获取到一个新的条件,
    即, 只要num[i]之前的最大值比之后的任意一个数字大2, 则这个序列就不是非递减序列。

  • 现在我们的目的就变成了证明这个序列不是非递减序列

步骤

  1. 定义变量max, 存储当前字符之前的最大数值, 初始化为0

  2. 遍历数组nums

    • 若nums[i]的值大于max, 则更新max的值
    • 若nums[i] - max的值小于-1, 即max比nums[i]大2, 则表示该序列不是非递减序列，直接返回”NO”
  3. 如果遍历结束后, 仍无法证明该序列不是非递减序列, 那它就是非递减序列, 则返回”YES”