665. Non-decreasing Array (Easy)
https://leetcode.com/problems/non-decreasing-array/
Given an array with n
integers, your task is to check if it could become non-decreasing by modifying at most 1
element.
We define an array is non-decreasing if array[i] <= array[i + 1]
holds for every i
(1 <= i="" <="" n).="" p="">
Example 1:
Input: [4,2,3] Output: True Explanation: You could modify the first4
to1
to get a non-decreasing array.
Example 2:
Input: [4,2,1] Output: False Explanation: You can't get a non-decreasing array by modify at most one element.
Note:
The n
belongs to [1, 10,000].
Solutions
class Solution {
// Find out the first descending pair and change it to conform the ascending order.
// Then move on the check whether this change makes the subsequence ascendingly ordered or not.
// We have two options of changing the value, slot i and i + 1. We update them in order and
// validate the sequence after manipulation respectively. As long as either of the two sequences are
// organized as ascending order, we can return true.
public boolean checkPossibility(int[] nums) {
if (nums.length <= 2) {
return true;
}
// It is wrongly described in the problem, we should take 0 position into account.
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] <= nums[i + 1]) {
continue;
}
int tmp = nums[i];
nums[i] = nums[i + 1];
if (checkAscending(nums)) {
return true;
}
nums[i] = tmp;
nums[i + 1] = tmp;
if (checkAscending(nums)) {
return true;
}
return false;
}
// Due to the fact that no descending pairs is found, return true directly.
return true;
}
public boolean checkAscending(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
return false;
}
}
return true;
}
}
Incorrect Solutions
class Solution {
// Incorrect idea of counting the descending pairs
public boolean checkPossibility(int[] nums) {
if (nums.length <= 2) {
return true;
}
// keep the count of decending pairs
int count = 0;
// It is wrongly described in the problem, we should take 0 position into accounnt.
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
count++;
}
}
if (count > 1) {
return false;
}
return true;
}
}