Halo

A magic place for coding

0%

LeetCode 解题报告(365) -- 665. Non-decreasing Array

Problem

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums [i] <= nums [i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

1
2
3
Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

1
2
3
Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

Constraints:

  • n == nums.length
  • 1 <= n <= 104
  • -105 <= nums [i] <= 105

Analysis

   题目给出一个数组要求在允许修改一个数值的情况下,判断这个数组是不是非递减的。从前往后遍历通过 nums [i - 1] > nums [i] 能判断出后面的数比前一个小,不符合题目的要求。

   一开始我的想法是直接判断上面出现的情况的次数,如果出现的次数超过一次则返回 false,但是其实是有问题的。比如 [3, 4, 2, 3] 这个数组,虽然只有 4 和 2 这一个地方满足了上面的条件,但实际上是不能通过只改变一个数字的值使得数组变成非递减的。因为无论把 4 修改成什么值,都无法做到。所以这里不能盲目地只判断出现的次数,还需要把实际更新的操作也做了,然后一直往后遍历下去。

   如何更新数值就是这道题目的难点所在。以题目给出的 Example1 为例,应该是把 4 改成 2,最后数组变成 [2,2,3];再看另一个例子 [-1,4,2,3],这里也是需要把 4 修改成为,最后数组变成 [-1,2,2,3];最后看一个例子 [2,3,3,2,4],这里并不是把 3 改成 2,而是把 2 修改成 3,最后数组变成 [2,3,3,3,4]。通过这三个例子,可以发现,前两个例子都是把 nums [i] 修改为 nums [i - 1],而最后一个例子是把 nums [i - 1] 修改成 nums [i]

   是什么导致了上面两种不同的修改方式呢?是 nums [i - 2] 这个数。Example1 是因为前面没有数字了,Example2 是因为 nums [i - 2] < nums [i],Example2 是因为 nums [i - 2] > nums [i],所以我们需要根据这个大小关系,选择不同的更新方法。

   同时维护一个 count 值,初始化为 1,当完成一次更新操作后,减 1,如果后面还有更新操作,则说明不满足题目的意思,直接 return false。


Solution

   无。


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int count = 1;
int size = nums.size ();
for (int i = 1; i < size; i++) {
if (nums [i - 1] > nums [i]) {
if (count <= 0) {
return false;
}
if (i == 1 || nums [i] >= nums [i - 2]) {
nums [i - 1] = nums [i];
} else {
nums [i] = nums [i - 1];
}
count--;
}
}
return true;
}
};

Summary

   这道题目虽然看上去意思很简单,但是实际打起来还是涉及到了一些细节。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels