[leetcode] 單調棧

本文總結單調棧演算法。

原問題

學習一個演算法,我們需要清楚的是:這個演算法最原始的問題背景是什麼樣的?

下一個更小元素

給定一個數組 nums,返回每個元素的下一個更小的元素的下標 res,即 res[i] 記錄的是 nums[i] 右端第一個比它小的元素的下標(不存在則為 -1 )。

例如 nums = [2,1,2,4,3],那麼 res = [1, -1, -1, 4, -1] .

從左往右掃描數組,棧底到棧頂維持嚴格升序,當掃描當前元素 nums[i] = x 時,如果需要出棧(說明棧頂大於等於當前的 x ),那麼 x 就是出棧元素的下一個更小元素。

vector<int> nextSmallerNumber(vector<int> &&nums)
{
    int n = nums.size(), idx = -1;
    vector<int> res(n, -1);
    stack<int> stk;
    for (int i = 0; i < n; i++)
    {
        while (!stk.empty() && nums[i] <= nums[stk.top()])
        {
            idx = stk.top(), stk.pop();
            res[idx] = i;
        }
        stk.emplace(i);
    }
    return res;
}

相關題目:

下一個更大元素

給定一個數組 nums,返回每個元素的下一個更大的元素的下標 res,即 res[i] 記錄的是 nums[i] 右端第一個比它大的元素的下標(不存在則為 -1 )。

例如 nums = [2,1,2,4,3],那麼 res = [3, 2, 3, -1, -1] .

從左往右掃描數組,棧底到棧頂維持降序(不要求嚴格),當掃描當前元素 nums[i] = x 時,如果需要出棧(說明棧頂嚴格小於當前的 x ),那麼 x 就是出棧元素的下一個更大元素。

vector<int> nextGreaterNumber(vector<int> &&nums)
{
    int n = nums.size(), idx;
    vector<int> res(n, -1);
    stack<int> stk;
    for (int i = 0; i < n; i++)
    {
        while (!stk.empty() && nums[stk.top()] < nums[i])
        {
            idx = stk.top(), stk.pop();
            res[idx] = i;
        }
        stk.emplace(i);
    }
    return res;
}

類似題目:

Leetcode

下一個更大元素 I

題目:496. 下一個更大元素 I

題目保證 nums1nums2 的子集,首先在 nums2 先做一次「下一個更大」元素,使用一個哈希表記錄結果。

然後掃描 nums1 ,把哈希表的結果按序填入數組 res 即可。

每次自己寫出了最優解,並且官方也是同一思路,都會覺得好有成就感 😄 。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) 
    {
        unordered_map<int,int> table;
        // 單調遞減棧,不需要嚴格遞減
        stack<int> stk;
        for (int x: nums2)
        {
            while (!stk.empty() && stk.top() < x)
            {
                table[stk.top()] = x;
                stk.pop();
            }
            stk.emplace(x);
        }
        int n = nums1.size();
        vector<int> res(n, -1);
        for (int i=0; i<n; i++)
        {
            if (table.count(nums1[i]))
                res[i] = table[nums1[i]];
        }
        return res;     
    }
};

下一個更大元素 II

題目:503. 下一個更大元素 II

這裡數組是一個 循環數組 ,那麼最簡單的處理方式當然就是令 nums = nums + nums 了,這樣做完一遍「下一個更大元素」之後,只需要截取 res 數組的前一半即可。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        if (nums.size() == 0) return {};
        nums.insert(nums.end(), nums.begin(), nums.end());
        int n = nums.size(), idx;
        vector<int> res(n, -1);
        stack<int> stk;  // 單調遞減棧,不需要嚴格遞減
        for (int i=0; i<n; i++)
        {
            while (!stk.empty() && nums[stk.top()] < nums[i])
            {
                idx = stk.top(), stk.pop();
                res[idx] = nums[i];
            }
            stk.push(i);
        }
        return vector<int>(res.begin(), res.begin() + n/2);
    }
};

那麼,有時候,面試官就對最優解非常苛刻(比如微軟),不允許我們使用這種額外空間,那麼就要使用取模的方式去模擬循環數組:

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        if (nums.size() == 0) return {};
        int n = nums.size(), idx;
        vector<int> res(n, -1);
        stack<int> stk;  // 單調遞減棧,不需要嚴格遞減
        for (int i=0; i<=2*n-1; i++)
        {
            while (!stk.empty() && nums[stk.top()] < nums[i % n])
            {
                idx = stk.top(), stk.pop();
                res[idx] = nums[i % n];
            }
            stk.push(i % n);
        }
        return res;
    }
};

結果模運算多了,時間效率還不如第一種。

每日溫度

題目:739. 每日溫度

本題就是「下一個更大元素」的裸題了,維持一個遞減棧(記錄下標)即可。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size(), idx = 0;
        vector<int> res(n, 0);
        stack<int> stk;   // 單調遞減棧
        for (int i=0; i<n; i++)
        {
            while (!stk.empty() && T[stk.top()] < T[i])
            {
                idx = stk.top(), stk.pop();
                res[idx] = i - idx;
            }
            stk.emplace(i);
        }
        return res;
    }
};

其他

兩側的更小值 I

題目:兩側的更小值

微軟的面試題 😭 ,這是套「下一個更小元素」的模版。此處不含重複元素

維持一個嚴格升序的棧,當掃描當前元素 nums[i] = x 時,如果需要出棧(說明棧頂大於等於當前的 x ),那麼 x 就是出棧元素的右側更小值。那麼,出棧元素的左側更小值在哪呢?就是它在棧中的鄰居。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<pair<int, int>> solve(vector<int> &nums)
{
    int n = nums.size(), idx;
    stack<int> stk; // 嚴格遞增棧
    vector<pair<int, int>> res(n, {-1, -1});
    for (int i = 0; i < n; i++)
    {
        while (!stk.empty() && nums[stk.top()] >= nums[i])
        {
            idx = stk.top(), stk.pop();
            res[idx].second = i;
            res[idx].first = (stk.empty() ? -1 : stk.top());
        }
        stk.push(i);
    }
    while (!stk.empty())
    {
        idx = stk.top(), stk.pop();
        res[idx].first = (stk.empty() ? -1 : stk.top());
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    vector<int> nums(n, 0);
    for (int i = 0; i < n; i++) cin >> nums[i];
    auto ans = solve(nums);
    for (auto [x,y]: ans) printf("%d %d\n", x, y);
}

兩側的更小值 II

題目:兩側的更小值 II

此處含有重複元素。

那麼我們還是維持一個遞增的棧(不要求嚴格),當掃描 nums[i] 時需要出棧,說明 nums[s.top()] 嚴格大於 nums[i],那麼就找到了 nums[s.top()] 的右側更小值是 nums[i]

那麼 nums[s.top()] 左側更小值在哪呢?是否就是在棧中的鄰居呢?答案是否定的。

比如輸入:[1, 3, 3, 1] . 當掃描到最後一個元素 1 的時候:

stk: 1 3 3 (1)
     ^      ^
     |      |
    left   cur

這時候顯然需要出棧,那麼兩個 3 的右側更小值都是 cur ,但棧頂的 3 的左側更小值不是它的鄰居(而是 left 指向的 1 )。

這時候,我們用一個 buf 把這樣 3 都記錄下來,那麼 buf 中的元素,它們的兩側更小值都是 {left, cur} 。如果 left 不存在(棧為空),那麼 left = -1

注意:程式碼實現中,棧存放的是下標。

程式碼實現

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<pair<int, int>> solve(vector<int> &nums)
{
    int n = nums.size(), idx;
    stack<int> stk; // 遞增棧,不要求嚴格
    vector<pair<int, int>> res(n, {-1, -1});
    for (int i = 0; i < n; i++)
    {
        while (!stk.empty() && nums[stk.top()] > nums[i])
        {
            idx = stk.top(), stk.top();
            vector<int> buf = {idx};
            while (!stk.empty() && nums[stk.top()] == nums[idx])
                buf.emplace_back(stk.top()), stk.pop();
            for (int x : buf)
            {
                res[x].first = (stk.empty() ? -1 : stk.top());
                res[x].second = i;
            }
        }
        stk.emplace(i);
    }
    while (!stk.empty())
    {
        idx = stk.top(), stk.top();
        vector<int> buf = {idx};
        while (!stk.empty() && nums[stk.top()] == nums[idx])
            buf.emplace_back(stk.top()), stk.pop();
        for (int x : buf)
            res[x].first = (stk.empty() ? -1 : stk.top());
    }
    return res;
}