Google
665 Non-decreasing Array

1. Question

Given an array withnintegers, your task is to check if it could become non-decreasing by modifyingat most1element.
We define an array is non-decreasing ifarray[i] <= array[i + 1]holds for everyi(1 <= i < n).
Example 1:
1
Input: [4,2,3]
2
3
Output: True
4
5
Explanation:
6
You could modify the first 4 to 1 to get a non-decreasing array.
Copied!
Example 2:
1
Input: [4,2,1]
2
3
Output: False
4
5
Explanation: You can't get a non-decreasing array by modify at most one element.
Copied!
Note:Thenbelongs to [1, 10,000].

2. Implementation

(1) DP (TLE)
Longest Increasing Subsequence的思想
1
class Solution {
2
public boolean checkPossibility(int[] nums) {
3
if (nums == null || nums.length <= 1) {
4
return true;
5
}
6
int n = nums.length;
7
int[] dp = new int[n];
8
Arrays.fill(dp, 1);
9
10
for (int i = 1; i < n; i++) {
11
for (int j = 0; j < i; j++) {
12
if (nums[j] <= nums[i] && (dp[j] + 1 > dp[i])) {
13
dp[i] = dp[j] + 1;
14
}
15
}
16
}
17
18
int maxLen = 1;
19
for (int i = 0; i < n; i++) {
20
maxLen = Math.max(maxLen, dp[i]);
21
}
22
return maxLen >= n - 1;
23
}
24
}
Copied!
(2) Greedy
思路: 要使得整个数组是非递减,我们用一个prev变量记录在nums[i]之前的最大数,用count记录递减的次数,显然当count大于等于2时,我们无法修改一次数组使其递增。如果nums[i] < prev, 这里有两种情况决定如何更新prev:
1.如果nums[i - 2]不存在或者nums[i - 2] > nums[i]时,由于nums[i] < prev已经出现一次递减情况, 为了避免再出现一次递减,保证nums在[i -2, i]的非递减性, 我们不更新prev, 这等价于将nums[i]变成prev
2.如果nums[i - 2] <= nums[i],为了保证nums[i - 2, i]的非递减性, 我们将prev更新为nums[i]
1
class Solution {
2
public boolean checkPossibility(int[] nums) {
3
if (nums == null || nums.length <= 1) {
4
return true;
5
}
6
7
int n = nums.length;
8
int count = 0;
9
int prev = nums[0];
10
11
for (int i = 1; i < n; i++) {
12
if (nums[i] < prev) {
13
++count;
14
15
if (count >= 2) {
16
return false;
17
}
18
19
if (i - 2 >= 0 && nums[i - 2] > nums[i]) continue;
20
21
}
22
prev = nums[i];
23
}
24
return true;
25
}
26
}
Copied!

3. Time & Space Complexity

DP: 时间复杂度O(n^2), 空间复杂度O(n)
Greedy: 时间复杂度O(n^2), 空间复杂度O(n)
Last modified 2yr ago