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:
Input: nums = [4,2,3] Output: true Explanation: You could modify the first4to1to get a non-decreasing array.
Example 2:
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.length1 <= n <= 104-105 <= nums[i] <= 105class Solution { public boolean checkPossibility(int[] nums) { // corner case if(nums == null || nums.length <= 1) return true; // the count of continuous non-decreasing sub-array int count = 1; int index = 0; int n = nums.length; for(int i = 1; i < n; i++){ if(nums[i] < nums[i - 1]){ index = i; count++; } } if(count == 1) return true; if(count == 2){ // if the discord happens at start or end position, we can modify // it to match the condition if(index == 1 || index == n - 1) return true; // if in the middle, we modify nums[index - 2] // index - 2, (index - 1, index) , index + 1 if(nums[index + 1] >= nums[index - 1] || nums[index] >= nums[index - 2]) { return true; } return false; } return false; } }
https://leetcode.com/problems/non-decreasing-array/discuss/106826/JavaC%2B%2B-Simple-greedy-like-solution-with-explanation
用count来表示non decreasing的subarray的数量，如果是1直接return true，如果大于2直接返回false。
如果是2，说明是两段。分两种情况，第一种要求转折点index有index + 1 >= index - 1, 或者index >= index - 2.
原文：https://www.cnblogs.com/wentiliangkaihua/p/14730966.html