單調(diào)棧解題模板如何秒殺三道算法題

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

本文就通過(guò)幾道算法題來(lái)看看單調(diào)棧模板的使用。

單調(diào)棧模板

首先，看一下 Next Greater Number 的原始問(wèn)題，這是力扣第 496 題「下一個(gè)更大元素 I」：

給你一個(gè)數(shù)組，返回一個(gè)等長(zhǎng)的數(shù)組，對(duì)應(yīng)索引存儲(chǔ)著下一個(gè)更大元素，如果沒(méi)有更大的元素，就存 -1。

函數(shù)簽名如下：

vector<int> nextGreaterElement(vector<int>& nums);

比如說(shuō)，輸入一個(gè)數(shù)組nums = [2,1,2,4,3]，你返回?cái)?shù)組[4,2,4,-1,-1]。

解釋?zhuān)旱谝粋€(gè) 2 后面比 2 大的數(shù)是 4; 1 后面比 1 大的數(shù)是 2；第二個(gè) 2 后面比 2 大的數(shù)是 4; 4 后面沒(méi)有比 4 大的數(shù)，填 -1；3 后面沒(méi)有比 3 大的數(shù)，填 -1。

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

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

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

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); // 存放答案的數(shù)組
    stack<int> s;
    // 倒著往棧里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        // 判定個(gè)子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮個(gè)起開(kāi)，反正也被擋著了。。。
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

這就是單調(diào)隊(duì)列解決問(wèn)題的模板。for 循環(huán)要從后往前掃描元素，因?yàn)槲覀兘柚氖菞５慕Y(jié)構(gòu)，倒著入棧，其實(shí)是正著出棧。while 循環(huán)是把兩個(gè)「?jìng)€(gè)子高」元素之間的元素排除，因?yàn)樗麄兊拇嬖跊](méi)有意義，前面擋著個(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一次，沒(méi)有任何冗余操作。所以總的計(jì)算規(guī)模是和元素規(guī)模n成正比的，也就是O(n)的復(fù)雜度。

問(wèn)題變形

單調(diào)棧的使用技巧差不多了，來(lái)一個(gè)簡(jiǎn)單的變形，力扣第 1118 題「一月有多少天」：

給你一個(gè)數(shù)組T，這個(gè)數(shù)組存放的是近幾天的天氣氣溫，你返回一個(gè)等長(zhǎng)的數(shù)組，計(jì)算： 對(duì)于每一天，你還要至少等多少天才能等到一個(gè)更暖和的氣溫；如果等不到那一天，填 0 。

函數(shù)簽名如下：

vector<int> dailyTemperatures(vector<int>& T);

比如說(shuō)給你輸入T = [73,74,75,71,69,76]，你返回[1,1,3,2,1,0]。

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

這個(gè)問(wèn)題本質(zhì)上也是找 Next Greater Number，只不過(guò)現(xiàn)在不是問(wèn)你 Next Greater Number 是多少，而是問(wèn)你當(dāng)前距離 Next Greater Number 的距離而已。

相同的思路，直接調(diào)用單調(diào)棧的算法模板，稍作改動(dòng)就可以，直接上代碼吧：

vector<int> dailyTemperatures(vector<int>& T) {
    vector<int> res(T.size());
    // 這里放元素索引，而不是元素
    stack<int> s; 
    /* 單調(diào)棧模板 */
    for (int i = T.size() - 1; i >= 0; i--) {
        while (!s.empty() && T[s.top()] <= T[i]) {
            s.pop();
        }
        // 得到索引間距
        res[i] = s.empty() ? 0 : (s.top() - i); 
        // 將索引入棧，而不是元素
        s.push(i); 
    }
    return res;
}

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

如何處理環(huán)形數(shù)組

同樣是 Next Greater Number，現(xiàn)在假設(shè)給你的數(shù)組是個(gè)環(huán)形的，如何處理？力扣第 503 題「下一個(gè)更大元素 II」就是這個(gè)問(wèn)題：

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

一般是通過(guò) % 運(yùn)算符求模（余數(shù)），來(lái)獲得環(huán)形特效：

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

這個(gè)問(wèn)題肯定還是要用單調(diào)棧的解題模板，但難點(diǎn)在于，比如輸入是[2,1,2,4,3]，對(duì)于最后一個(gè)元素 3，如何找到元素 4 作為 Next Greater Number。

對(duì)于這種需求，常用套路就是將數(shù)組長(zhǎng)度翻倍 ：

這樣，元素 3 就可以找到元素 4 作為 Next Greater Number 了，而且其他的元素都可以被正確地計(jì)算。

有了思路，最簡(jiǎn)單的實(shí)現(xiàn)方式當(dāng)然可以把這個(gè)雙倍長(zhǎng)度的數(shù)組構(gòu)造出來(lái)，然后套用算法模板。但是， 我們可以不用構(gòu)造新數(shù)組，而是利用循環(huán)數(shù)組的技巧來(lái)模擬數(shù)組長(zhǎng)度翻倍的效果 。

直接看代碼吧：

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);
    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;
}

這樣，就可以巧妙解決環(huán)形數(shù)組的問(wèn)題，時(shí)間復(fù)雜度O(N)。