Leetcode刷題學習筆記 – Monotonic Stack

簡介

stack中保持著一定的順序，例如遞增或是遞減。
如果要新增的element比top還大/小。就把top pop出去。然後繼續往下比，直到保持一定的遞增或是遞減的順序。通常是找序列中比自己後面，但是值比自己還大/小的題目。

使用時機?

1. 需要往前或是往後尋找，下一個比自己大或比自己小的元素就可以使用monotonic stack

PLE(Previous Less Element)

Good reference : Sum of Subarray Minimums

找出之前比自己還小的值。

• stack 存放index。因為存index有很多好處，其中之一就是可以算和target的差距。
• 如果stack為empty則填入-1，也是有利計算差距。

vector<int> nums;
vector<int> ple(nums.size());
stack<int> st; // 存放index
for(int i = 0; i < nums.size(); ++i) {
    while(!st.empty() && nums[st.top()] > nums[i]) st.pop();
    ple[i] = st.empty() ? -1 : st.top();
    st.push(i); // 將目前index推入stack
}

NLE(Next less element)

找出之後比自己還小的值。

• code snippet一樣，只是for反過來尋找
• 如果stack為empty則填入nums.size()

vector<int> nums;
int sz = nums.size();
vector<int> nle(sz);
stack<int> st;
for(int i = nums.size() - 1; i >= 0; --i) {
    while(!st.empty() && nums[st.top()] > nums[i]) st.pop();
    nle[i] = st.empty() ? sz : st.top();
    st.push(i);
}

另一種寫法，如果沒辦法從後面走訪數列的話

vector<int> nums;
int sz = nums.size();
vector<int> nle(sz, sz);
stack<int> st;
for(int i = 0; i < sz; ++i) {
    while(!st.empty() && nums[st.top()] > nums[i]) {
        nle[st.top()] = i;
        st.pop();
    }
    st.push(i);    
}

2. 往前或是往後看的最大/小值

剛剛第一種情況是往前或是往後看，第一個比自己大或小的值。另一種情況是往前看或是往後看，找出最大值。如果自己本身是最大值就是自己。

以下的code是從自己往後看，看到最大值的index。

vector<int> nums;
int sz = nums.size();
vector<int> bwdMax(sz); // index
stack<int> st; // index
for(int i = 0; i < sz; ++i) {
    // stack中比目前的值還小，就丟掉，因為接下來的index只會看到這個
    while(!st.empty() && nums[i] >= nums[st.top()]) st.pop();
    if(st.empty()) st.push(i); // 如果沒了就是看到自己
    bwdMax[i] = st.top();
}

以下的code使從自己往前看，看到最大值的index。

vector<int> nums;
int sz = nums.size();
vector<int> fwdMax(sz); // index
stack<int> st; // index
for(int i = sz - 1; i >= 0; --i) {
    while(!st.empty() && nums[i] >= nums[st.top()]) st.pop();
    if(st.empty()) st.push(i);
    fwdMax[i] = st.top();
}

後來想想，其實找fordward max或是backward max不需要使用stack，只要用以下簡單的方法即可。

int maxv = -1;
vector<int> bwd(sz);
for(int i = 0; i < sz; ++i) {
    maxv = max(maxv, nums[i]);
    bwd[i] = maxv;
}

Example

42. Trapping Rain Water

給你一個vector<int> height，下雨過後會有多少雨水留在裡面。

1. 雨水留在裡面的多少會由，這格往前往後看的最大值決定。
2. 所以使用monotonic stack來計算每格往前往後看的最大值。

class Solution {
public:
    int trap(vector<int>& height) {
        auto sz = height.size();
        stack<int> st;
        vector<int> bwdMax(sz), fwdMax(sz);
    
        // backward max value index
        for(int i = 0; i < sz; ++i) {
            while(!st.empty() && height[i] >= height[st.top()])  st.pop();
            if(st.empty()) st.push(i);
            bwdMax[i] = st.top();
        }

        // clean the stack
        while(!st.empty()) st.pop();

        // forward max value index
        for(int i = sz - 1; i >= 0; --i) {
            while(!st.empty() && height[i] >= height[st.top()]) st.pop();
            if(st.empty()) st.push(i);
            fwdMax[i] = st.top();
        }

        // calculate each rain
        int ans{0};
        for(int i = 0; i < sz; ++i) {
            ans += min(height[fwdMax[i]], height[bwdMax[i]]) - height[i];
        }

        return ans;
    }
};

也可以使用以下簡單的方法

class Solution {
public:
    int trap(vector<int>& height) {
        int sz = height.size();
        vector<int> fwd(sz), bwd(sz);
        int maxv = -1;
        for(int i = 0; i < sz; ++i) {
            maxv = max(maxv, height[i]);
            bwd[i] = maxv;
        }
        maxv = -1;
        for(int i = sz - 1; i >= 0; --i) {
            maxv = max(maxv, height[i]);
            fwd[i] = maxv;
        }
        int ans{0};
        for(int i = 0; i < sz; ++i) {
            ans += min(fwd[i], bwd[i]) - height[i];
        }
        return ans;
    }
};

739. Daily Temperatures[Medium]

給你一個每日溫度的數列vector<int> temperatures。求出過給天後，會比現在還溫暖。例如：
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

解題思路：

這是一個典型的單調遞增stack的問題。

vector<int> dailyTemperatures(vector<int>& temperatures) {
    stack<pair<int, int>> st;   // 使用pair來紀錄
    auto n = temperatures.size();
    vector<int> ans(n, 0);
        
    for(int i = 0; i < n; ++i) {
        if(!st.empty()) {
            while(!st.empty() && temperatures[i] > st.top().first) {
                auto item = st.top();
                ans[item.second] = i - item.second;
                st.pop();
            }
        }
        st.push({temperatures[i], i});
    }
        
    return ans;
}

2022/07/06
和上面的相比，stack只需存index即可。
2022/10/29
因為這題是找出後面第一個比自己大的值，所以是monotonic stack

vector<int> dailyTemperatures(vector<int>& temp) {
    stack<int> s; //index
    int sz = temp.size();
    vector<int> rtn(sz);
    for(int i = sz - 1; i >= 0; --i) {
        while(!s.empty() && temp[i] >= temp[s.top()])
            s.pop();
        rtn[i] = s.empty() ? 0 : s.top() - i;
        s.push(i);
    }
    return rtn;
}

901. Online Stock Span

找出price左邊連續比它還小的數值。

1. 一開始有想到monotone stack但是怎麼寫都是不對。原因是少了一個變數。這邊使用了stack<pair<int, int>>。多了一個資訊。統計這個數字的span。全部的span加起來剛好是輸入price的個數。
2. 使用monotone stack是因為不需要找比自己還大的數字。
3. 可以看成我們在整理這個vector
   [100]
   [100, 80]
   [100, 80, 60]
   [100, 80, [60, 70]] –> [100, 80, 70(2)]
   [100, 80, 70(2), 60]
   [100, 80, [70(2), 60, 75]] –> [100, 80, 75(4)]
   [100, [80, 75(4), 85]] –> [100, 85(6)]

class StockSpanner {
    stack<pair<int, int>> st; // value, span
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        int ret{1};
        while(!st.empty() && st.top().first <= price) {
            ret += st.top().second;
            st.pop();
        }
        st.emplace(price, ret);
        return ret;
    }
};

2022/10/29
因為這題是找出前面比自己還要大的數，所以使用monotonic stack。

class StockSpanner {
    vector<int> prices;
    stack<int> st;
    int idx{0};
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        while(!st.empty() && prices[st.top()] <= price) st.pop();
        int rtn = st.empty() ? idx + 1: idx - st.top();
        prices.push_back(price);
        st.push(idx);
        idx++;
        return rtn;
    }
};

3. 找出以第i個位置的山峰或是山谷

應用前面的找出前面和後面比自己高或是比自己低的位置，如果左右邊都應用的話，就是找出以第i個位置的山峰或是山谷。
例如: [1,4,3,7,4,5]，可以畫出以下的圖

這邊可以發現，對index = 2 來說，如果以他為local minimal的subarray，可以得到。

同理，對index = 4來說，以他為local minimal的subarray，可以得到

Example

1793. Maximum Score of a Good Subarray

Maximum score的定義是，subarray的最小值，乘上subarray的長度。另外Good subarray的定義是，必須包含index = k。

1. 因為Score的定義是，subarray的最小值乘上長度。所以算是找local minimal => 使用monotonic stack找出區域山谷。
2. 最後看每個index所構成的區域山谷，使否有包含index = k。

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int sz = nums.size();
        vector<int> left(sz, -1), right(sz, sz), st;
        for(int i = 0; i < sz; ++i) {
            while(!st.empty() && nums[i] < nums[st.back()]) {
                right[st.back()] = i;
                st.pop_back();
            }
            st.push_back(i);
        }
        st.clear();
        for(int i = sz - 1; i >= 0; --i) {
            while(!st.empty() && nums[i] < nums[st.back()]) {
                left[st.back()] = i;
                st.pop_back();
            }
            st.push_back(i);
        }
        int ans{};
        for(int i = 0; i < sz; ++i) {
            if(left[i] < k && right[i] > k)
                ans = max(ans, nums[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }
};

84. Largest Rectangle in Histogram

找出histogram中最大面積的長方形。

1. 因為長方形的高度會被，最矮的數值決定。=> 找出以此index的區域山谷。
2. 找出以每個index為山谷之後，就可以依序找出每個面積，得到最大值。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int sz = heights.size();
        vector<int> fle(sz, sz), ble(sz, -1);
        stack<int> st;
        for(int i = 0; i < sz; ++i) {
            while(!st.empty() && heights[i] < heights[st.top()]) {
                fle[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        st = move(stack<int>());
        for(int i = sz - 1; i >= 0; --i) {
            while(!st.empty() && heights[i] < heights[st.top()]) {
                ble[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        int ans{};
        for(int i = 0; i < sz; ++i) {
            int left = i - ble[i];
            int right = fle[i] - i;
            ans = max(ans, heights[i] * (left + right - 1));
        }
        return ans;
    }
};

Problems

907. Sum of Subarray Minimums

給你一個vector<int>找出所有subarray的組合中，每個subarray的最小值的和為多少?

• 這題參考了 Sum of Subarray Minimums 對monotinic stack有更深一層的了解。
• 另外參考了官神的答案，因為官神對於計算個數比較直覺。
  計算個數參考以下的註解。
• 因為要知道subarray最小值，所以某個subarray的最小值取決於，這個subarray的左邊和右邊數值都是比目前的值還要大。
• 找出自己前面和後面的最小值 ==> monotonic stack
• why two pass? 因為條件和自己前後都有關係。

    // [3, 1, 2, 4]
    // [3]          --> ans += 3， 找出比自己小的左右兩邊的邊界
    // [3, 1], [1], [1, 2], [1, 2, 4], [3, 1, 2], [3, 1, 2, 4] --> ans += 1
    // [2], [2, 4] --> ans += 2
    // [4] --> ans += 4
int sumSubarrayMins(vector<int>& arr) {
    int sz = arr.size();
    vector<int> ple(sz), nle(sz);
        
    // PLE
    stack<int> st;
    for(int i = 0; i < sz; ++i) {
        while(!st.empty() && arr[st.top()] > arr[i]) st.pop();
        ple[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    // clear the stack
    while(!st.empty()) st.pop();
    // NLE
    // 為什麼是大於等於?
    // 因為等於的最小值也是和arr[i]一樣。
    // 但是如果，兩邊都使用>= 會有重複問題，所以只要一邊就可以。
    // ex : [71, 55, 82, 55], 如果ple和nle都使用>=
    // idx1 [71, 55], [55],
    //                     [82], [82, 55]
    // idx3 [71, 55, 82, 55] -->重複計算
    for(int i = sz - 1; i >= 0; --i) {
        while(!st.empty() && arr[st.top()] >= arr[i]) st.pop();
        nle[i] = st.empty() ? sz : st.top();
        st.push(i);
    }

    // count the result
    //   [3, 1, 2, 4]
    // -1,  ,1        ,4
    //   i - ple[i] : 前面有幾個element : 2 --> [1], [3, 1]
    //   nle[i] - i : 後面有幾個element : 3 --> [], [2], [2, 4]
    long rtn{0};
    long mod = 1e9 + 7;
    for(int i = 0; i < sz; ++i) {
        long count = (i - ple[i]) * (nle[i] - i) % mod;
        rtn = (rtn + arr[i] * count) % mod;
    }

    return rtn;
}                                                      

316. Remove Duplicate Letters

class Solution {
public:
    string removeDuplicateLetters(string s) {
        stack<char> st;
        unordered_set<char> seen;
        unordered_map<char, int> last; // 最後出現的位置
        for(int i = 0; i < s.size(); ++i) last[s[i]] = i;
        for(int i = 0; i < s.size(); ++i) {
            if(seen.count(s[i])) continue;
            // 目前的char比s[i]還大，且後面還會有，就丟掉
            while(!st.empty() && s[i] < st.top() && last[st.top()] > i) {
                seen.erase(st.top());
                st.pop();
            }
            seen.insert(s[i]);
            st.push(s[i]);
        }
        string rtn{};
        while(!st.empty()) {
            rtn = st.top() + rtn;
            st.pop();
        }
        return rtn;
    }
};

2866. Beautiful Towers II

給你一個vector<int> maxHeights，當用每個index當成mountain array的top，則兩邊勢必要配合top做修正，修正完之後才會成為mountain array，返回最大的mountain array sum。

1. 參考官方答案。
2. 我們把每個index都當成mountain top。
3. 如果兩邊遇到比自己大的就會變成maxHeights[i]。所以可以容易計算出sum += (j - i) * maxHeights[i];
4. 遇到比自己小的(j)，則會被j的左邊或是右邊的sum決定。
5. 所以問題變成找出比自己小的index。
6. 另外卡住的點是，以前使用monotonic stack會在pop之後更新資料，但是現在是pop完之後才處理，所以方向改變了。

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int sz = maxHeights.size();
        vector<long long> right(sz), left(sz);
        stack<int> st;
        for(int i = 0; i < sz; ++i) {
            while(!st.empty() && maxHeights[i] < maxHeights[st.top()])
                st.pop();
            if(st.empty()) left[i] = (long long)(i + 1) * maxHeights[i];
            else left[i] = left[st.top()] + (long long)(i - st.top()) * maxHeights[i];
            st.push(i);
        }
        st = move(stack<int>());
        long long res{};
        for(int i = sz - 1; i >= 0; --i) {
            while(!st.empty() && maxHeights[i] < maxHeights[st.top()])
                st.pop();
            if(st.empty()) right[i] = (long long)(sz - i) * maxHeights[i];
            else right[i] = right[st.top()] + (long long)(st.top() - i) * maxHeights[i];
            st.push(i);
            res = max(res, left[i] + right[i] - maxHeights[i]);
        }
        return res;
    }
};

1944.Number of Visible People In a Queue

1. 這題感覺就是monotonic stack的題目，但是就是思考不出來怎麼處理中間比較矮的人。
2. 參考lee215解答

class Solution {
    // 題目是往右看，可以看到幾個人
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int sz = heights.size();
        vector<int> res(sz), st;
        for(int i = 0; i < sz; ++i) {
            // 前一個比自己小的(st.back())，因為會被我擋住(i)，
            // 所以丟出來，不用在比了
            while(!st.empty() && heights[st.back()] <= heights[i]) 
                res[st.back()]++, st.pop_back();
            // 前一個比自己大的(st.back())可以看到自己(i)
            if(!st.empty()) 
                res[st.back()]++;
            st.push_back(i);
        }
        return res;
    }
};

tags: leetcode 刷題