LeetCode665 Non-decreasing Array


题目

LeetCode665 Non-decreasing Array

思路

判断只修改一个数能否使得数组非递减.

首先计算数组从左往右能延伸的距离$l$,从右往左能延伸的距离$r$.

可行的情况有:

  • $ r \leq l $
  • $r == l + 1$ 且 满足下列情况之一
    • r 为最后一位
    • l位置的值 $ \leq $ r + 1位置的值
    • l为首位
    • l-1位置的值 $ \leq $ r 位置的值

代码

1
2
3
4
5
6
7
8
9
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int siz = nums.size(), l = 0, r = siz - 1;
while (l + 1 < siz && nums[l] <= nums[l + 1]) l++;
while (r > 0 && nums[r - 1] <= nums[r]) r--;
return r <= l || (r == l + 1 && ((nums[l] <= nums[r + 1] || r == siz - 1) || (l == 0 || nums[l - 1] <= nums[r])));
}
};