LeetCode演算法題-Non-decreasing Array（Java實現）
這是悅樂書的第283 次更新，第300 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第151題（順位題號是665）。給定一個包含n個整數的陣列，您的任務是通過修改最多1個元素來檢查它是否可以變為非遞減。如果array [i] <= array [i + 1]，且0 <= i <n，則我們定義一個數組是非遞減的。例如：
輸入：[4,2,3]
輸出：true
說明：可以修改4為1或2以獲得非遞減陣列。
輸入：[4,2,1]
輸出：false
說明：通過最多修改一個元素，無法獲得非遞減陣列。
注意：n的範圍在[1,1,000]。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
題目的意思是能否只在一步內，將原陣列變成一個非遞減的陣列，也就是遞增的陣列，並且元素之間的關係是小於等於，即nums[i] <= nums[i+1]，0 <= i < n。
特殊情況：陣列內的元素小於等於兩個，直接返回true。
正常情況：什麼情況下，需要修改原陣列元素的值？當前元素比前一個元素小的時候，這時我們需要進一步判斷，是改當前元素還是改前一個元素？是改大還是改小？
如果當前元素小於其前一個元素：
第一種情況，如果當前元素是陣列的第二個元素，改當前元素的前一個元素，前一個元素往小改，將當前元素的值賦值給當前元素的前一個元素；
第二種情況，如果當前元素比其前前個元素值要大，前一個元素往小改，將當前元素的值賦值給當前元素的前一個元素；
第三種情況，當第一和第二種情況都不滿足的時候，當前元素往大改，將當前元素的前一個元素值賦值給當前元素。
每改一次都要記數，如果在for迴圈中count大於1，直接返回false，最後也需要判斷count是否小於等於1。
public boolean checkPossibility(int[] nums) {
if (nums.length <= 2) {
return true;
}
int count = 0;
for (int i=1; i<nums.length; i++) {
if (nums[i] < nums[i-1]) {
if (count > 1) {
return false;
}
if (i == 1 || nums[i] >= nums[i-2]) {
nums[i-1] = nums[i];
} else {
nums[i] = nums[i-1];
}
count++;
}
}
return count <= 1;
}
03 第二種解法
我們也可以不修改原陣列的原始值。先使用一個迴圈，找到當前陣列中需要修改的元素的索引值，做個標記，然後判斷該標記是否以下幾種情況：
第一：標記還是初始值，說明該陣列是一個遞增陣列，不用修改任何元素就能滿足題目要求。
第二：標記等於0，即第一個元素需要修改，也就是說陣列中只有第一個元素大於第二個元素，從第二個元素開始，陣列是遞增的，只用修改第一個元素就能是整個陣列遞增。
第三：標記等於陣列倒數第二個索引，也就是說倒數第二個元素大於倒數第一個元素，也只需要改一個元素即可。
第四：標記所在元素的前一個、後一個元素之間的關係是小於等於，而標記所在的元素大於後一個元素，所以也只用該標記所在的元素即可。
第五：標記所在的元素比其下下個元素要小或者相等，而標記所在元素比下一個元素要大，也只需要改小標記所在元素即可。
如果是上面這五種情況，表示都符合題目的要求，如果不滿足，直接返回false。
public boolean checkPossibility2(int[] nums) {
if (nums.length <= 2) {
return true;
}
// 初始化索引值為-1
int index = -1;
for (int i=0; i<nums.length-1; i++) {
// 如果當前元素比後一個元素大，說明遇到了需要修改的元素
if (nums[i] > nums[i+1]) {
// 如果索引值為-1，表示是第一次遇到需要修改的元素，否則表示已經多次遇到需要修改的值了
if (index == -1) {
// 將其索引賦值給index
index = i;
} else {
return false;
}
}
}
// index為-1表示原陣列本身就是個遞增陣列，為0表示，只用修改第一個元素即可，為nums.length-2表示只用修改倒數第二個元素即可
if (index == -1 || index == 0 || index == nums.length-2) {
return true;
}
// index所在元素的前後元素是小於等於的關係
if (nums[index-1] <= nums[index+1]) {
return true;
}
// index所在元素的小於等於其下下個元素
if (nums[index] <= nums[index+2]) {
return true;
}
return false;
}
04小結
演算法專題目前已日更超過四個月 ，演算法題文章151 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！