每天一道leetcode665-非递减数列

来自:程序员乔戈里(微信号:CXYqiaogeli),作者:Be a fresh man

665_(非递减数列)Non-decreasing Array

1 问题描述、输入输出与样例

1.1 问题描述

给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。

说明:  

n 的范围为 [1, 10,000]。

1.2 输入与输出

输入:

  • vector

    & nums:输入的整数数组

输出:

  • bool:在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列

1.3 样例

1.3.1 样例1

输入: [4,2,3]

输出: True

解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

1.3.2 样例2

输入: [4,2,1]

输出: False

解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

2 思路描述与代码

2.1 思路描述(比较计数法)

cnt统计当前数比前一个数小的个数;
遍历数组中所有的值

  • 如果当前值比前一个值小

    • 如果cnt == 1,则判断是否存在纠正的方式,无则返回false

    • 否则cnt >= 2,则不存在纠正方式,返回false  

2.2 代码

bool checkPossibility(vector<int>& nums) {
   int n = nums.size();
   int cnt = 0;
   for (int i = 1; i < n; i++) {
       if (nums[i - 1] > nums[i]) {
           cnt++;
           //cnt = 1时,需要注意有两种情况可以补救:
           //1. 比如[-1 4 2 3], 4 < 2, 2 > -1, 通过修改 4  为 -1~2 间的数都可以补救
           //2. 比如[1 2 -1 3],-1 < 2, 2 < 3,  通过修改 -1 为  2~3 间的数都可以补救

           //cnt >= 2则怎样都不行了,因为只能修改一次
           if((cnt == 1 && i >= 2 && i < n - 1 && nums[i] < nums[i - 2] && nums[i + 1] < nums[i - 1]) || cnt >= 2return false;
       }
   }
   return true;
}

3 思考与拓展

3.1 思考

本题中需要考虑多种情况的可能性,否则容易犯错。

3.1.1 其他方法

无。

3.1.2 复杂度分析

方法空间复杂度时间复杂度
比较计数法O(1)O(n)

3.1.3 难点分析

  1. 当前值比前一个值小只出现一次时需要考虑[-1 4 2 3]、[1 2 -1 3]、[1,2,3,2]、[4,1,2,3]之类可纠正的情况

3.2 拓展

如果给你的是链表数据呢?

推荐↓↓↓
算法与数据结构
上一篇:每天一道leetcode122-买卖股票的最佳时机 II 下一篇:每天一道leetcode-392判断子序列