先給題
給你一個長度為 n 的整數陣列，請你判斷在 最多 改變 1 個元素的情況下，該陣列能否變成一個非遞減數列，
我們是這樣定義一個非遞減數列的： 對于陣列中所有的 i (0 <= i <= n-2)，總滿足 nums[i] <= nums[i + 1]，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/non-decreasing-array
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
1.暴力破解
這個就不談了，保證第i個值小于等于后面的所有元素，如果有不符合的，數量不超過1就行，
2.根據條件判斷
我們要避免逐個進行比較，現在我們來討論如何避免，
我們先不把那一個改變1個元素考慮在內，我們遇到的數列要么符合非遞減數列，要么不符合，符合的自然不用說了，那么不符合的我們肯定會遇到至少一個 a b（a b 代之兩個元素）b<a，
我們遇到第一個a b 就分情況判斷能否改變 a 或者 b 中的一個值 來讓它符合非遞減數列，如果不能 那么就回傳0，如果可以，那么接下來就不能再出現a b（a b 代之兩個元素）b<a這樣的情況，如果出現了，不需要討論，直接回傳0即可，
所以我們要在遇到第一個a b 的時候進行一下討論，a和b要改變哪一個元素的數值，是由周圍元素決定的，
我們知道 a>b 那么如果b后面沒有元素，只需要讓b增大即可，即此時 i == nums.size()-1 直接回傳1即可，
如果b后面有元素c的情況呢，我們又要分兩種情況c>=a 和 c <a，
c>=a 那么我們只需要讓b變大就可以成為一個非遞減數列，結束第一輪尋找a b，開啟第二輪尋找a b，
c < a 的話 我們又要分兩種情況 c < b 和c >=b，
c < b 則 a b c 是遞減的，怎么更換也無法達成條件 回傳0.
c >=b 那么我們要降低a的值就可以達成條件，而a的值必須<=b 即 a 可調的最大值是b，又分出兩種情況 a前面有元素d和a前面沒有元素d，
a前面沒有元素d 即 a是第一個元素 a只要改變的值<=b就可以，是可以交換的，結束第一輪尋找a b，開啟第二輪尋找a b，
a前面有元素d 如果想要達成條件，a可變的最大值一定要大于 d 所以又分了兩種情況，
b >= d，是可以交換的，結束第一輪尋找a b，開啟第二輪尋找a b，
b < d， a即便改變成b，也無法達成非遞減數列的條件 回傳0.
第二輪判斷就簡單了，只要遇到 a b這樣的情況 直接回傳0就可以了，
直接上代碼了，注釋我認為寫的蠻清楚了，
bool checkPossibility(vector<int>& nums) {
int i = 1;
for (; i < nums.size(); i++) {
//當出現后者小于前者的情況時 即 a b
if(nums[i] < nums[i - 1]) {
//判斷此時是不是最后一位，沒有c 可以改變b，并且是最后一位 回傳1
if(i == nums.size() - 1)
return 1;
//此時是 a b c這種情況
//c >= a 可以改變b 繼續
else if (nums[i + 1] >= nums[i - 1])
break;
//c < a
//c < b 連續三個數是遞減的 不可能更換
else if (nums[i +1] < nums[i])
return 0;
//c >= b
//a 前面沒有d 可以改變a
else if (i == 1)
break;
//a 前面有d 判斷是否可以改變a
//a可改變的值是a <= b a最大變為b 那么就判斷b和d的關系
else if(nums[i] >= nums[i - 2])
break;
//b < d 無法改變
else
return 0;
}
}
i++;
for (; i < nums.size(); i++) {
//第二次出現直接回傳flase
if(nums[i] < nums[i - 1]) {
return 0;
}
}
return 1;
}
時間和記憶體通過是通過了，效率也不錯，但是代碼太復雜了，分的情況太多，那么接下來去看題解吧，
3.按照題解
思考題解所說的是貪心演算法
如果不符合題意的數列（不考慮更換），肯定會遇到a b，a >b，這和我開始的思想是一樣的，
要么讓a 變小，要么讓 b 變大，那采取哪一種策略呢？我想的是去尋找周圍元素，來判斷它可不可以變，而我忽略了可以先讓它變成適當的數，再去與周圍的環境比較，（這樣我們就沒必要考慮c了，后續中肯定可以涉及到c）
這里就用到了貪心演算法了，變化哪個影響是最小的呢，如果a可以變小的話那肯定是讓a變小，因為前面已經確定了，a變小是不影響后面的判斷的，如果a不能變小，我們也只能增大b，讓b = a，然后繼續讓b與后續去比較，
只要a是第一個數，或者b的值>=a的前一個值，我們就可以讓a 變小，
如果a不是第一個數且b的值<a，我們只能讓b的值增大（我做的時候忽略了這兩種條件其實包括了全部的情況）
修改后的代碼
bool checkPossibility(vector<int>& nums) {
int flag = 1;//標記為可以交換
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (!flag)
return 0;
flag = 0;
//開始交換
if (i == 0 || nums[i + 1] >= nums[i - 1])
nums[i] = nums[i + 1];
else
nums[i + 1] = nums[i];
}
}
return 1;
}
https://leetcode-cn.com/problems/non-decreasing-array/solution/cyu-yan-tan-xin-si-xiang-by-liu-xiang-3-ia2u/
https://leetcode-cn.com/problems/non-decreasing-array/solution/yi-ding-yao-rang-ni-nong-dong-wei-shi-ya-u9te/
這是我參考的兩個題解，如果還有不懂得可以去看一下，講的很好，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258002.html
標籤：其他