java如何實現非下降數組

這篇文章主要介紹“java如何實現非下降數組”，在日常操作中，相信很多人在java如何實現非下降數組問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java如何實現非下降數組”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

題目描述

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

樣例1：

ⅰ 輸入： [4,2,3]

ⅱ 輸出： True

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

樣例2：

ⅰ 輸入： [4,2,1]

ⅱ 輸出： False

ⅲ 說明： 無法通過修改至多一個元素使數組變為非下降的。

解題思路分析

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

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

參考程序

Java版本：

到此，關于“java如何實現非下降數組”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！