陣列A = [a0，a1，a2，a3，a4，....，an-1]代表每個山峰的峰高。用
分治法 找到每個山峰左邊比自己更高的山峰和右邊比自己更高的山峰的
索引位置 。例如：
Input: A=[1,3,2,7,4,9]
Output:
L=[None, None, 2, None, 3, None] R=[1, 3, 3, 5, 5, None]。描述演算法和分析時間復雜度。
uj5u.com熱心網友回復：
如果可以用O(n)的空間,時間復雜度能到O(n),不用分治法
從左往右掃描時,保存從高到低的高峰資訊
開始時空,
讀第一個 '1',因是空,結果為None,把'1'保存;
讀第二個 '3',跟保存值比較,沒有比3大的,結果為None,用'3'替換保存的'1'
讀第三個 '2',跟保存的'3'比較,比3小,結果為3,把2保存起來
讀第四個 '7',根保存的'3','2'比較,結果為None, 用7替換掉保存的3和2
......
再類似地從右往左掃描一次
uj5u.com熱心網友回復：
參考 1 樓 android2008 的回復: 如果可以用O(n)的空間,時間復雜度能到O(n),不用分治法
你可能對O(n)的理解有誤，你這演算法是O(n^2)，不是O(n)。遍歷你的兩個陣列也需要時間代價的……
真正O(n)的演算法是利用單調堆疊這個資料結構。
啥叫單調堆疊請自行網上搜索。
一個單調遞增堆疊，一個單調遞減堆疊，分別存左和右。然后兩個陣列LR分別記錄結果
先從左到右遍歷一遍，用單調遞減堆疊記錄左邊高的峰。比堆疊頂低就記錄到L并入堆疊，否則回圈出堆疊，然后記錄到L。
再從右到左遍歷一遍，用單調遞增堆疊記錄右邊高的峰。同理。
uj5u.com熱心網友回復：
參考 3 樓 lx3275852 的回復: Quote: 參考 1 樓 android2008 的回復:
每次比較次數多于1時都會洗掉 (比較次數-1)的資料, 怎么不是O(N)了? 不知道你說的O(N^2)結論怎么得出的。
uj5u.com熱心網友回復：
參考 4 樓 android2008 的回復: 每次比較次數多于1時都會洗掉 (比較次數-1)的資料, 怎么不是O(N)了? 不知道你說的O(N^2)結論怎么得出的。
那也許是我沒太看懂你的演算法描述。
根據你的描述，每次遇到比你存的數字大的時候，都需要遍歷找，然后替換成你的這個數字啊……
你寫的第四步，“讀第四個 '7',根保存的'3','2'比較,結果為None, 用7替換掉保存的3和2”
到7的時候，要替換3和2，這不是就需要遍歷一遍了么。。
uj5u.com熱心網友回復：
參考 5 樓 lx3275852 的回復: Quote: 參考 4 樓 android2008 的回復:
也許我說的不清楚.
看起來是每次都要遍歷一遍,但比較次數最多也就2N次,因為每次不需要遍歷到底,而且遍歷的越多,則洗掉的越多.
比如當前保存了5個: 10 8 6 4 2, 新資料是9,雖然要比較5次,但8,6,4,2都會被洗掉,保留的只有 10,9,后面遍歷時長度就小了.
uj5u.com熱心網友回復：
參考 6 樓 android2008 的回復: 也許我說的不清楚.
服了you，你這次描述的不就是單調堆疊么，和我3L說的有啥區別。。。
但你這個描述，單調堆疊不描述就算了，遞增遞減不描述，堆疊也不描述……
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/60768.html
標籤：數據結構與算法
上一篇：什么軟體能夠決議音頻并且輸出下面格式的檔案，跪求大神指導！
下一篇：Vue 專案提示沒有引入JavaScript
