题目

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. Input: nums = [4,2,3]
  2. Output: true
  3. Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 10^4
  • -105 <= nums[i] <= 10^5

题意

给定一个数组，判断能否通过改变其中一个或零个数，使整个数组构成非递减序列。

思路

遍历数组，找到第一个i，使得 nums[i] > nums[i+1]，这时我们尝试进行修复，有两种情况，要么改变nums[i]，要么改变nums[i+1]：(1) i - 1 >= 0 且 nums[i-1] > nums[i+1]，这时为了保证非递减，必须使 nums[i+1] = nums[i]; (2) i == 0 或者 nums[i-1] <= nums[i+1] 时，为了在之后的遍历中尽可能保证非递减，nums[i+1]必须尽可能的小，所以使 nums[i] = nums[i+1]。完成修复后，我们已经保证了子数组 [0 ~ i+1] 是一个非递减序列，且已经动用了唯一的修改机会，只要继续向后遍历判断是否仍存在 nums[j] > nums[j+1] 的情况即可。

代码实现

Java

  1. class Solution {
  2.     public boolean checkPossibility(int[] nums) {
  3.         boolean found = false;
  4.         for (int i = 0; i + 1 < nums.length; i++) {
  5.             if (nums[i] > nums[i + 1]) {
  6.                 if (found) return false;
  7.                 found = true;
  8.                   // 因为只有改变nums[i+1]才会影响之后的遍历，可以省略改变nums[i]的情况
  9.                 if (i > 0 && nums[i - 1] > nums[i + 1]) nums[i + 1] = nums[i];
  10.             }
  11.         }
  12.         return true;
  13.     }
  14. }