Sign in

[Java][Greedy][LeetCode] Non-decreasing Array #665

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 first 4 to 1 to get a non-decreasing array.

One by one to look for the point that happen decreasing. The counter will +1 when the event was happened. Because array can be modified one time. So, if count>1, return false to end of this procedure.
In order to remain the array is non-decreasing array. when the event happen, I need to check previous element. Assume current point is [i], previous point is [i-1], and so on. If [i-2]<=[i], I need to replace value of [i] to [i-2]. If [i-2]>[i], I need to replace value of [i-1] to [i]. As mention above, array will keep in ascending order. But, keep an important in mind. when counter>1 will return false.

逐一尋找發生不是屬於逐漸升高的事件發生點,每次發生就counter +1,因為只能改1次,所以當counter>1就表示已經要改超過1次,這時直接return false結束這個歷遍。
事件發生的時候,為了能讓數組保持升序,就要再往前比較數值,當前位置為[i],前一個即為[i-1],再往前即為[i-2],假設[i-2]的數值<=[i],則表示將[i-1]改數值為[i],假設[1–2]>[i],則表示要將[i]改數值為[i-1],如此即可將數組保持升序,但保持一個重點,如果counter>1,就可以結束這個判斷了。