九章演算法 | Google 面試題：非下降數組

03-04

撰文 | Ben助教 & 施助教

專欄 | 九章演算法

題目描述

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

樣例1：

ⅰ 輸入： [4,2,3]ⅱ 輸出： Trueⅲ 說明：可以把第一個數4修改為1，得到[1,2,3]為非下降的數組最長上升子序列ⅲ 說明：可以把第一個數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版本：

面試官角度分析

這題是一道簡單難度的題，只需分析出去掉一個數後能形成非下降數組的原數組應該有怎樣的性質，即可設計相應的演算法，做法可以有很多種。給出正確的演算法即可hire。

lintcode相關問題

http://www.lintcode.com/zh-cn/problem/longest-increasing-subsequence/