你有一個整數陣列。
在一個步驟中，您可以將某個索引處的值更改為任何整數值。使陣列不減少的最少步數是多少？
例如 1：
如果陣列是 [8, 12, 11, 15],
我們可以將索引 2 處的值從 11 更改為 13。然后陣列變為 [8, 12, 13, 15]
因此，不需要步驟數 = 1；
例如2：
如果陣列是 [9, 2, 5, 18, 20, 25, 19],
我們可以將索引 0 處的值從 9 更改為 2，將索引 6 處的值從 19 更改為 30。然后陣列變為 [2, 2, 5, 18, 20, 25, 30]
因此，不需要步驟數 = 2；
例如 3：
如果陣列是 [9, 11, 5, 7]，
我們可以將索引 2 處的值從 5 更改為 11，將索引 3 處的值從 7 更改為 11。然后陣列變為 [9, 11, 11, 11]
因此，不需要步驟數 = 2；
例如 4：
如果陣列是 [13, 12, 10, 7, 6],
進行更改后，陣列變為 [13, 13, 13, 13, 13] 或 [6, 7, 10, 12, 13]。有辦法做到這一點。
因此，不需要步驟數 = 4；
我嘗試的一種方法是找到所有遞減的子序列并將它們的長度 -1 添加到名為ans. 然后歸還。但它在上面提到的 Eg 3 中失敗了。如何解決這個問題？
uj5u.com熱心網友回復：
我認為這個問題相當于在序列中找到最長的非遞減鏈。
將每個索引 i 作為圖的節點。那么節點 i 有一個指向節點 j 的箭頭，當且僅當 i < j 且 L[i] <= L[j]。然后，您需要使用圖論中的技術找到圖中最長的路徑。
由于條件 i<j，您不會得到回圈。
uj5u.com熱心網友回復：
正如@sfx 所提到的，這相當于找到最長的非遞減子序列。您可以使用Patience 排序找到此子序列的長度。
維基百科的演算法：
- 發的第一張牌形成一個由單張牌組成的新牌堆。
- 隨后的每張牌都放置在一些現有牌堆上，其頂牌的價值不小于新牌的價值，或者放在所有現有牌堆的右側，從而形成一個新牌堆。
- 當沒有更多的牌可以處理時，游戲結束。
使用您的示例 3：
[9, 11, 5, 7]
插入[9]：
[9]
插入[11]：輸出陣列中沒有大于或等于[11]的值，所以再添加一個堆疊：
[9, 11]
插入[5]：第一個大于等于[5]的值是[9]，所以替換[9]：
[5, 11]
插入[7]：第一個大于等于[7]的值是[11]，替換[11]：
[5, 7]
輸出陣列的長度是最長非遞減子序列的長度。使整個序列不減少的運算元等于輸入陣列中的元素數減去該子序列的長度。
使用二分搜索來確定放置下一個值的位置，這種方法的最壞情況時間復雜度是O(n log n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350518.html
上一篇：搜索字串自定義函式演算法