java怎么實(shí)現(xiàn)非下降數(shù)組

給出包含n個(gè)整數(shù)的數(shù)組，你的任務(wù)是檢查它是否可以通過修改至多一個(gè)元素變成非下降的。一個(gè)非下降的數(shù)組array對(duì)于所有的i（1<=i<n）滿足array[i-1]<=array[i]。n屬于區(qū)間[1,10000]。

樣例1：

ⅰ 輸入： [4,2,3]

ⅱ 輸出： True

ⅲ 說明： 可以把第一個(gè)數(shù)4修改為1，得到[1,2,3]為非下降的數(shù)組

樣例2：

ⅰ 輸入： [4,2,1]

ⅱ 輸出： False

ⅲ 說明： 無法通過修改至多一個(gè)元素使數(shù)組變?yōu)榉窍陆档摹?/p>

a. 簡單的思考可以得到，情況無非為三種：不需要修改就滿足條件的、修改一個(gè)元素可滿足條件的和修改一個(gè)元素也無法滿足條件的。對(duì)于第一種情況，只需遍歷數(shù)組看是否滿足數(shù)組的每一項(xiàng)都大于等于前一項(xiàng)，滿足則返回true。對(duì)于第二種情況，可以枚舉要修改的那個(gè)數(shù)array[i]，再去檢查array[i]之前的數(shù)是否是非下降的，array[i]之后的數(shù)是否是非下降的，最后還應(yīng)該檢查array[i-1]<=array[i+1]是否成立（如果array[i]位于邊界則無需檢查），如果成立則可以將array[i]改為array[i-1]和array[i+1]之間的任何數(shù)使數(shù)組變?yōu)榉窍陆禂?shù)組，這是情況二，返回true，如果對(duì)于所有的i都不成立，則為情況三，返回false。這樣做的時(shí)間復(fù)雜度為O(n^2)，額外空間復(fù)雜度為O(1)。

b. 修改一個(gè)數(shù)以后可以變成非下降的數(shù)組滿足什么條件呢？顯然，這樣的數(shù)組應(yīng)當(dāng)滿足只存在一對(duì)相鄰的數(shù)不滿足非下降的條件，即只存在唯一的i（1<=i<n）滿足array[i-1]>array[i]，可以斷言，如果這樣的i存在多個(gè)，則原數(shù)組無法通過修改至多一個(gè)數(shù)變?yōu)榉窍陆禂?shù)組。那么是否滿足這個(gè)條件的數(shù)組都可以通過修改一個(gè)數(shù)而滿足非下降呢？不是的，比如[2,4,1,3]，只有相鄰的4,1不滿足非下降，但它不能通過只改變一個(gè)數(shù)變?yōu)榉窍陆怠Ｆ鋵?shí)，如果只存在一個(gè)i滿足array[i-1]>array[i]，那么要修改的那個(gè)數(shù)一定在array[i-1]和array[i]這兩個(gè)數(shù)之中，那么就可以套用上一種做法，對(duì)于兩種情況分別進(jìn)行判斷即可。更進(jìn)一步地來說，由于只有對(duì)于i才有array[i-1]>array[i]成立，所以別的所有相鄰的數(shù)均滿足非下降的條件，因此對(duì)于array[i-1]來說，它之前和它之后的數(shù)組均分別滿足非下降的條件，對(duì)于array[i]亦是如此，所以，只需判斷前后兩段數(shù)組能否可以接成非下降的數(shù)組即可。具體來說，如果要修改的數(shù)是array[i-1]，那么只需判斷array[i-2]<=array[i]是否成立，同樣的如果要修改array[i]，那么應(yīng)判斷array[i-1]<=array[i+1]是否成立，當(dāng)然如果array[i-1]或array[i]位于邊界則直接成立?？偨Y(jié)該算法：統(tǒng)計(jì)所有不滿足非下降的相鄰位置的個(gè)數(shù)count，如果count為0，則返回true（不用修改），若count大于1，則返回false，否則應(yīng)進(jìn)行進(jìn)一步的判斷：設(shè)不滿足非下降的位置為i，array[i-1]>array[i]，則最終返回true的條件為array[i-1]、array[i]為邊界或者array[i-2]<=array[i]或者array[i-1]<=array[i+1]。時(shí)間復(fù)雜度為O(n)，額外空間復(fù)雜度為O(1)。

Java版本：