我正在嘗試撰寫一個程式，其輸入是一個整數陣列及其大小。此代碼必須洗掉小于左側元素的元素。我們希望找到重復此操作的次數，從而無法洗掉更多元素。這是我的代碼，它有效，但我希望它更快。
您是否有任何想法使此代碼更快，或者其他比這更快的方法？
例如，給定陣列 [10, 9, 7, 8, 6, 5, 3, 4, 2, 1]，函式應該回傳 2 因為 [10,9,7,8,6,5,3,4 ,2,1] → [10,8,4] → [10]
int numberOfTimes(int array[] , int n) {
int count = 0;
int flag = 0;
int sizeCounter = 0;
while (true){
for (int i = 0; i < n-1; i) {
if (array[i]<= array[i 1]){
sizeCounter ;
array[sizeCounter] = array[i 1];
} else{
flag = 1;
}
}
if (flag == 0)
return count;
count ;
flag = 0;
n = (sizeCounter 1);
sizeCounter = 0;
}
}
uj5u.com熱心網友回復：
這個問題可以使用“單調堆疊”在 O(n) 時間和 O(n) 空間中解決。
對于 的每個元素，array我們將找到洗掉元素所需的“動作/回合”數。換句話說，必須經過多少圈，以便洗掉當前元素（包括）和最靠近左側的較大元素之間的所有元素。
如果我們知道這個數字（我們稱之為turns），那么我們可以為陣列的所有元素找到這個值的最大值，我們就會知道從陣列中洗掉所有可以洗掉的元素所需的輪數。我們會有我們的答案。
現在，我們如何找到該turns值？這很容易，如果我們turns為當前元素左側的所有元素計算這些值。我們只是找到比當前元素大的最接近的元素，并找到該turns元素和當前元素之間的每個元素的最大數量。即，如果當前元素在 index 處i，并且最近的較大元素在 index j( j < iand array[j] > array[i]) 處，則turns[i] = max(turns[k] 1), for k in [j 1..i-1]。
如果我們天真地這樣做，找到turns每個元素將是 O(n)。幸運的是，它很容易地看到，當我們發現j了一些i，我們永遠不會需要考慮元素之間j和i不斷試。請記住，array[j] > array[i]之間的一切j和i小于array[i]。我們正在尋找最接近的大于某個值的陣列元素，因此，如果array[i]不是答案，整個[j 1..i-1]范圍也不是答案，我們可以直接轉到j。
考慮到這一點，我們到達了單調堆疊。我們不是turns為 的每個元素array存盤，而是只為array我們迄今為止訪問過的嚴格遞減的子序列存盤它。
在向堆疊添加新元素之前，首先我們需要洗掉每個小于當前元素的元素。然后堆疊的頂部將是我們的array[j].
由于每個元素都添加到堆疊中并恰好洗掉一次，因此每個元素的攤銷成本turns為 O(1)，因此整個演算法為 O(n)。在最壞的情況下，堆疊的大小增長到與陣列相同的大小（如果array嚴格減少）。所以空間復雜度是O(n)。
這是代碼（python）：
array = [10, 9, 7, 8, 6, 5, 3, 4, 2, 1]
s = [] # monotonic stack of pairs (array[j],turns[j])
count = 0 # result: number of turns to delete all deletable elements
for el in array:
# initially assuming current element can be deleted
turns = 1
# peeking at the top of the stack
while len(s) > 0 and s[-1][0] <= el:
_,t = s.pop()
turns = max(t 1, turns)
# corner case: current element is the largest so far, cant be deleted
if len(s) == 0:
turns = 0
s.append( (el, turns) )
count = max(count, turns)
print(count)
測驗：
[10, 9, 7, 8, 6, 5, 3, 4, 2, 1] → 2
[10, 9, 7, 8, 6, 5, 3, 4, 2, 1, 9] → 3
[10, 9, 7, 8, 6, 5, 3, 4, 2, 1, 11] → 2
[] → 0
[1, 2, 3] → 0
[1, 2, 3, 1] → 1
[10, 1, 2, 3, 4, 5] → 5
UPD：我剛剛閱讀了評論，我想向 @wLui155 致敬，他在我之前提出了相同的核心想法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/333555.html
上一篇：Mysql查詢優化