首頁>技術>

讀完本文,你可以去力扣拿下如下題目:

496.下一個更大元素I

503.下一個更大元素II

1118.一月有多少天

-----------

棧(stack)是很簡單的一種資料結構,先進後出的邏輯順序,符合某些問題的特點,比如說函式呼叫棧。

單調棧實際上就是棧,只是利用了一些巧妙的邏輯,使得每次新元素入棧後,棧內的元素都保持有序(單調遞增或單調遞減)。

聽起來有點像堆(heap)?不是的,單調棧用途不太廣泛,只處理一種典型的問題,叫做 Next Greater Element。本文用講解單調佇列的演算法模版解決這類問題,並且探討處理「迴圈陣列」的策略。

首先,講解 Next Greater Number 的原始問題:給你一個數組,返回一個等長的陣列,對應索引儲存著下一個更大元素,如果沒有更大的元素,就存 -1。不好用語言解釋清楚,直接上一個例子:

給你一個數組 [2,1,2,4,3],你返回陣列 [4,2,4,-1,-1]。

解釋:第一個 2 後面比 2 大的數是 4; 1 後面比 1 大的數是 2;第二個 2 後面比 2 大的數是 4; 4 後面沒有比 4 大的數,填 -1;3 後面沒有比 3 大的數,填 -1。

這道題的暴力解法很好想到,就是對每個元素後面都進行掃描,找到第一個更大的元素就行了。但是暴力解法的時間複雜度是 O(n^2)。

這個問題可以這樣抽象思考:把陣列的元素想象成並列站立的人,元素大小想象成人的身高。這些人面對你站成一列,如何求元素「2」的 Next Greater Number 呢?很簡單,如果能夠看到元素「2」,那麼他後面可見的第一個人就是「2」的 Next Greater Number,因為比「2」小的元素身高不夠,都被「2」擋住了,第一個露出來的就是答案。

這個情景很好理解吧?帶著這個抽象的情景,先來看下程式碼。

vector<int> nextGreaterElement(vector<int>& nums) {    vector<int> ans(nums.size()); // 存放答案的陣列    stack<int> s;    for (int i = nums.size() - 1; i >= 0; i--) { // 倒著往棧裡放        while (!s.empty() && s.top() <= nums[i]) { // 判定個子高矮            s.pop(); // 矮個起開,反正也被擋著了。。。        }        ans[i] = s.empty() ? -1 : s.top(); // 這個元素身後的第一個高個        s.push(nums[i]); // 進隊,接受之後的身高判定吧!    }    return ans;}

這就是單調佇列解決問題的模板。for 迴圈要從後往前掃描元素,因為我們藉助的是棧的結構,倒著入棧,其實是正著出棧。while 迴圈是把兩個“高個”元素之間的元素排除,因為他們的存在沒有意義,前面擋著個“更高”的元素,所以他們不可能被作為後續進來的元素的 Next Great Number 了。

這個演算法的時間複雜度不是那麼直觀,如果你看到 for 迴圈巢狀 while 迴圈,可能認為這個演算法的複雜度也是 O(n^2),但是實際上這個演算法的複雜度只有 O(n)。

分析它的時間複雜度,要從整體來看:總共有 n 個元素,每個元素都被 push 入棧了一次,而最多會被 pop 一次,沒有任何冗餘操作。所以總的計算規模是和元素規模 n 成正比的,也就是 O(n) 的複雜度。

現在,你已經掌握了單調棧的使用技巧,來一個簡單的變形來加深一下理解。

給你一個數組 T = [73, 74, 75, 71, 69, 72, 76, 73],這個陣列存放的是近幾天的天氣氣溫(這氣溫是鐵板燒?不是的,這裡用的華氏度)。你返回一個數組,計算:對於每一天,你還要至少等多少天才能等到一個更暖和的氣溫;如果等不到那一天,填 0 。

舉例:給你 T = [73, 74, 75, 71, 69, 72, 76, 73],你返回 [1, 1, 4, 2, 1, 1, 0, 0]。

你已經對 Next Greater Number 型別問題有些敏感了,這個問題本質上也是找 Next Greater Number,只不過現在不是問你 Next Greater Number 是多少,而是問你當前距離 Next Greater Number 的距離而已。

相同型別的問題,相同的思路,直接呼叫單調棧的演算法模板,稍作改動就可以啦,直接上程式碼把。

vector<int> dailyTemperatures(vector<int>& T) {    vector<int> ans(T.size());    stack<int> s; // 這裡放元素索引,而不是元素    for (int i = T.size() - 1; i >= 0; i--) {        while (!s.empty() && T[s.top()] <= T[i]) {            s.pop();        }        ans[i] = s.empty() ? 0 : (s.top() - i); // 得到索引間距        s.push(i); // 加入索引,而不是元素    }    return ans;}

單調棧講解完畢。下面開始另一個重點:如何處理「迴圈陣列」。

同樣是 Next Greater Number,現在假設給你的陣列是個環形的,如何處理?

給你一個數組 [2,1,2,4,3],你返回陣列 [4,2,4,-1,4]。擁有了環形屬性,最後一個元素 3 繞了一圈後找到了比自己大的元素 4 。

首先,計算機的記憶體都是線性的,沒有真正意義上的環形陣列,但是我們可以模擬出環形陣列的效果,一般是透過 % 運算子求模(餘數),獲得環形特效:

int[] arr = {1,2,3,4,5};int n = arr.length, index = 0;while (true) {    print(arr[index % n]);    index++;}

回到 Next Greater Number 的問題,增加了環形屬性後,問題的難點在於:這個 Next 的意義不僅僅是當前元素的右邊了,有可能出現在當前元素的左邊(如上例)。

明確問題,問題就已經解決了一半了。我們可以考慮這樣的思路:將原始陣列“翻倍”,就是在後面再接一個原始陣列,這樣的話,按照之前“比身高”的流程,每個元素不僅可以比較自己右邊的元素,而且也可以和左邊的元素比較了。

怎麼實現呢?你當然可以把這個雙倍長度的陣列構造出來,然後套用演算法模板。但是,我們可以不用構造新陣列,而是利用迴圈陣列的技巧來模擬。直接看程式碼吧:

vector<int> nextGreaterElements(vector<int>& nums) {    int n = nums.size();    vector<int> res(n); // 存放結果    stack<int> s;    // 假裝這個陣列長度翻倍了    for (int i = 2 * n - 1; i >= 0; i--) {        while (!s.empty() && s.top() <= nums[i % n])            s.pop();        res[i % n] = s.empty() ? -1 : s.top();        s.push(nums[i % n]);    }    return res;}

12
最新評論
  • BSA-TRITC(10mg/ml) TRITC-BSA 牛血清白蛋白改性標記羅丹明
  • Dubbo3.0 來了:服務發現百萬叢集,可伸縮微服務架構