Formatted question description: https://leetcode.ca/all/665.html
665. Non-decreasing Array (Easy)
Given an array nums
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 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 first4
to1
to 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:
1 <= n <= 10 ^ 4
- 10 ^ 5 <= nums[i] <= 10 ^ 5
Related Topics:
Array
Solution 1.
// OJ: https://leetcode.com/problems/non-decreasing-array/
// Time: O(N)
// Space: O(1)
class Solution {
public:
bool checkPossibility(vector<int>& A) {
for (int i = 1, cnt = 0; i < A.size(); ++i) {
if (A[i] >= A[i - 1]) continue;
if (++cnt > 1) return false;
if (i - 2 < 0 || min(A[i], A[i - 1]) >= A[i - 2]) A[i] = A[i - 1] = min(A[i], A[i - 1]);
else A[i] = A[i - 1] = max(A[i], A[i - 1]);
}
return true;
}
};
Java
-
class Solution { public boolean checkPossibility(int[] nums) { int length = nums.length; boolean flag = false; for (int i = 1; i < length; i++) { int prevNum = nums[i - 1], curNum = nums[i]; if (prevNum > curNum) { if (flag) return false; else { if (i > 1 && i < length - 1) { int prev2Num = nums[i - 2], nextNum = nums[i + 1]; if (curNum < prev2Num && nextNum < prevNum) return false; } flag = true; } } } return true; } }
-
// OJ: https://leetcode.com/problems/non-decreasing-array/ // Time: O(N) // Space: O(1) class Solution { public: bool checkPossibility(vector<int>& A) { int N = A.size(), R = N - 2; for (; R >= 0 && A[R] <= A[R + 1]; --R); for (int i = 0; i < N; ++i) { if ((i == 0 || i == N - 1 || A[i + 1] >= A[i - 1]) && i >= R) return true; if (i - 1 >= 0 && A[i] < A[i - 1]) break; } return false; } };
-
class Solution(object): def checkPossibility(self, nums): """ :type nums: List[int] :rtype: bool """ flag = False pre = float("-inf") for i in range(len(nums) - 1): if nums[i] < pre: if nums[i + 1] >= nums[i - 1]: nums[i] = nums[i + 1] else: nums[i - 1] = nums[i] flag = True break pre = nums[i] if not flag and len(nums) > 1 and nums[-1] < nums[-2]: nums[-1] = nums[-2] pre = float("-inf") for num in nums: if num < pre: return False pre = num return True