Welcome to Subscribe On Youtube
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.
-
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; } } ############ class Solution { public boolean checkPossibility(int[] nums) { for (int i = 0; i < nums.length - 1; ++i) { int a = nums[i], b = nums[i + 1]; if (a > b) { nums[i] = b; if (isSorted(nums)) { return true; } nums[i] = a; nums[i + 1] = a; return isSorted(nums); } } return true; } private boolean isSorted(int[] nums) { for (int i = 0; i < nums.length - 1; ++i) { if (nums[i] > nums[i + 1]) { return false; } } 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: def checkPossibility(self, nums): """ :type nums: List[int] :rtype: bool """ if len(nums) < 2: return True count = 0 for i in range(1, len(nums)): if nums[i] < nums[i - 1]: if count == 1: return False if not ( i + 1 == len(nums) or nums[i + 1] >= nums[i - 1] or i - 2 < 0 or nums[i - 2] < nums[i] ): return False else: count = 1 return True ############ 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
-
func checkPossibility(nums []int) bool { isSorted := func(nums []int) bool { for i, b := range nums[1:] { if nums[i] > b { return false } } return true } for i := 0; i < len(nums)-1; i++ { a, b := nums[i], nums[i+1] if a > b { nums[i] = b if isSorted(nums) { return true } nums[i] = a nums[i+1] = a return isSorted(nums) } } return true }
-
function checkPossibility(nums: number[]): boolean { const isSorted = (nums: number[]) => { for (let i = 0; i < nums.length - 1; ++i) { if (nums[i] > nums[i + 1]) { return false; } } return true; }; for (let i = 0; i < nums.length - 1; ++i) { const a = nums[i], b = nums[i + 1]; if (a > b) { nums[i] = b; if (isSorted(nums)) { return true; } nums[i] = a; nums[i + 1] = a; return isSorted(nums); } } return true; }