java怎麼實作非下降數組

題目描述

#給出包含n個整數的數組，你的任務是檢查它是否可以透過修改至多一個元素變成非下降的。一個非下降的陣列array對於所有的i（1

範例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]位於邊界則無需檢查），如果成立則可以將array[i]改為array[i-1]和array[i 1]之間的任何數使數組變為非下降數組，這是情況二，返回true，如果對於所有的i都不成立，則為情況三，返回false。這樣做的時間複雜度為O(n^2)，額外空間複雜​​度為O(1)。

b. 修改一個數以後可以變成非下降的陣列滿足什麼條件呢？顯然，這樣的陣列應滿足只存在一對相鄰的數不滿足非下降的條件，即只存在唯一的i（1array[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]，則最終傳回true的條件為array[i-1]、array[i]為邊界或array[i-2]

參考程式

#Java版本：

#########

以上是java怎麼實作非下降數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！