單調(diào)棧實(shí)際上就是棧，只是利用了一些巧妙的邏輯，使得每次新元素入棧后，棧內(nèi)的元素都保持有序（單調(diào)遞增或單調(diào)遞減）。

聽起來(lái)有點(diǎn)像堆（heap）？不是的，單調(diào)棧用途不太廣泛，只處理一種典型的問題，叫做 Next Greater Element。本文用講解單調(diào)隊(duì)列的算法模版解決這類問題，并且探討處理「循環(huán)數(shù)組」的策略。

首先，講解 Next Greater Number 的原始問題：給你一個(gè)數(shù)組，返回一個(gè)等長(zhǎng)的數(shù)組，對(duì)應(yīng)索引存儲(chǔ)著下一個(gè)更大元素，如果沒有更大的元素，就存 -1。不好用語(yǔ)言解釋清楚，直接上一個(gè)例子：

給你一個(gè)數(shù)組 [2,1,2,4,3]，你返回?cái)?shù)組 [4,2,4,-1,-1]。

解釋：第一個(gè) 2 后面比 2 大的數(shù)是 4; 1 后面比 1 大的數(shù)是 2；第二個(gè) 2 后面比 2 大的數(shù)是 4; 4 后面沒有比 4 大的數(shù)，填 -1；3 后面沒有比 3 大的數(shù)，填 -1。

這道題的暴力解法很好想到，就是對(duì)每個(gè)元素后面都進(jìn)行掃描，找到第一個(gè)更大的元素就行了。但是暴力解法的時(shí)間復(fù)雜度是 O(n^2)。

這個(gè)問題可以這樣抽象思考：把數(shù)組的元素想象成并列站立的人，元素大小想象成人的身高。這些人面對(duì)你站成一列，如何求元素「2」的 Next Greater Number 呢？很簡(jiǎn)單，如果能夠看到元素「2」，那么他后面可見的第一個(gè)人就是「2」的 Next Greater Number，因?yàn)楸取?」小的元素身高不夠，都被「2」擋住了，第一個(gè)露出來(lái)的就是答案。

這個(gè)情景很好理解吧？帶著這個(gè)抽象的情景，先來(lái)看下代碼。

這就是單調(diào)隊(duì)列解決問題的模板。for 循環(huán)要從后往前掃描元素，因?yàn)槲覀兘柚氖菞５慕Y(jié)構(gòu)，倒著入棧，其實(shí)是正著出棧。while 循環(huán)是把兩個(gè)“高個(gè)”元素之間的元素排除，因?yàn)樗麄兊拇嬖跊]有意義，前面擋著個(gè)“更高”的元素，所以他們不可能被作為后續(xù)進(jìn)來(lái)的元素的 Next Great Number 了。

這個(gè)算法的時(shí)間復(fù)雜度不是那么直觀，如果你看到 for 循環(huán)嵌套 while 循環(huán)，可能認(rèn)為這個(gè)算法的復(fù)雜度也是 O(n^2)，但是實(shí)際上這個(gè)算法的復(fù)雜度只有 O(n)。

分析它的時(shí)間復(fù)雜度，要從整體來(lái)看：總共有 n 個(gè)元素，每個(gè)元素都被 push 入棧了一次，而最多會(huì)被 pop 一次，沒有任何冗余操作。所以總的計(jì)算規(guī)模是和元素規(guī)模 n 成正比的，也就是 O(n) 的復(fù)雜度。

現(xiàn)在，你已經(jīng)掌握了單調(diào)棧的使用技巧，來(lái)一個(gè)簡(jiǎn)單的變形來(lái)加深一下理解。

給你一個(gè)數(shù)組 T = [73, 74, 75, 71, 69, 72, 76, 73]，這個(gè)數(shù)組存放的是近幾天的天氣氣溫（這氣溫是鐵板燒？不是的，這里用的華氏度）。你返回一個(gè)數(shù)組，計(jì)算：對(duì)于每一天，你還要至少等多少天才能等到一個(gè)更暖和的氣溫；如果等不到那一天，填 0 。

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

解釋：第一天 73 華氏度，第二天 74 華氏度，比 73 大，所以對(duì)于第一天，只要等一天就能等到一個(gè)更暖和的氣溫。后面的同理。

你已經(jīng)對(duì) Next Greater Number 類型問題有些敏感了，這個(gè)問題本質(zhì)上也是找 Next Greater Number，只不過現(xiàn)在不是問你 Next Greater Number 是多少，而是問你當(dāng)前距離 Next Greater Number 的距離而已。

相同類型的問題，相同的思路，直接調(diào)用單調(diào)棧的算法模板，稍作改動(dòng)就可以啦，直接上代碼把。

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;
}

單調(diào)棧講解完畢。下面開始另一個(gè)重點(diǎn)：如何處理「循環(huán)數(shù)組」。

同樣是 Next Greater Number，現(xiàn)在假設(shè)給你的數(shù)組是個(gè)環(huán)形的，如何處理？

給你一個(gè)數(shù)組 [2,1,2,4,3]，你返回?cái)?shù)組 [4,2,4,-1,4]。擁有了環(huán)形屬性，最后一個(gè)元素 3 繞了一圈后找到了比自己大的元素 4 。

首先，計(jì)算機(jī)的內(nèi)存都是線性的，沒有真正意義上的環(huán)形數(shù)組，但是我們可以模擬出環(huán)形數(shù)組的效果，一般是通過 % 運(yùn)算符求模（余數(shù)），獲得環(huán)形特效：

回到 Next Greater Number 的問題，增加了環(huán)形屬性后，問題的難點(diǎn)在于：這個(gè) Next 的意義不僅僅是當(dāng)前元素的右邊了，有可能出現(xiàn)在當(dāng)前元素的左邊（如上例）。

明確問題，問題就已經(jīng)解決了一半了。我們可以考慮這樣的思路：將原始數(shù)組“翻倍”，就是在后面再接一個(gè)原始數(shù)組，這樣的話，按照之前“比身高”的流程，每個(gè)元素不僅可以比較自己右邊的元素，而且也可以和左邊的元素比較了。

怎么實(shí)現(xiàn)呢？你當(dāng)然可以把這個(gè)雙倍長(zhǎng)度的數(shù)組構(gòu)造出來(lái)，然后套用算法模板。但是，我們可以不用構(gòu)造新數(shù)組，而是利用循環(huán)數(shù)組的技巧來(lái)模擬。直接看代碼吧：

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n); // 存放結(jié)果
    stack<int> s;
    // 假裝這個(gè)數(shù)組長(zhǎng)度翻倍了
    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;
}