Stack

先進後出的容器，有以下幾個常見的操作：

push 頂端加入元素
pop 頂端刪除元素
top 回傳頂端元素
empty 確認是否為空
size 回傳元素個數

Monotonic Stack

解題時常用的技巧，保持 Stack 裡面的元素是單調遞減或遞增，也有可能是儲存對應的下標，本文章中的遞增或遞減順序是由 Stack 底部至頂部，有的文章中偏好使用頂部至底部，故在此做區分。

分類

遞增 Stack

內部的值由底部至頂部為遞增。

當前值大於 Stack 頂部值：直接插入 Stack 中。
當前值小於 Stack 頂部值：不斷移除頂部值，直到當前值大於 Stack 頂部值或是 Stack 為空，最後插入當前值。

Code:

stack<int> stk;
vector<int> input;
for(int i = 0; i < input.size(); i++){
    while(!stk.empty() && stk.top() > input[i]){
        stk.pop();
    }
    stk.push(input[i]);
}

遞減 Stack

內部的值由底部至頂部為遞減。

當前值小於 Stack 頂部值：直接插入 Stack 中。
當前值大於 Stack 頂部值：不斷移除頂部值，直到當前值小於 Stack 頂部值或是 Stack 為空，最後插入當前值。

Code:

stack<int> stk;
vector<int> input;
for(int i = 0; i < input.size(); i++){
    while(!stk.empty() && stk.top() < input[i]){
        stk.pop();
    }
    stk.push(input[i]);
}

應用

Monotonic Stack 主要用來尋找 某元素左/右兩邊，第一個比該元素大/小的元素，簡單來說可以分為以下四類，而他們也都有自己對應的處理方式。

元素左側，第一個比該元素大的元素：
建立一個遞減的 Stack，由左向右遍歷，插入當前元素時，位於頂部的元素即為所求，如果 Stack 為空，代表左側沒有比該元素大的元素。
元素左側，第一個比該元素小的元素：
建立一個遞增的 Stack，由左向右遍歷，插入當前元素時，位於頂部的元素即為所求，如果 Stack 為空，代表左側沒有比該元素小的元素。
元素右側，第一個比該元素大的元素：
- 建立一個遞減的 Stack，由左向右遍歷，當元素自 Stack 中移除時，要插入的元素即為所求，如果沒有被移除，代表右側沒有比該元素大的元素。
- 建立一個遞增的 Stack，由右向左遍歷，插入當前元素時，位於頂部的元素即為所求，如果 Stack 為空，代表右側沒有比該元素大的元素。
元素右側，第一個比該元素小的元素：
- 建立一個遞增的 Stack，由左向右遍歷，當元素自 Stack 中移除時，要插入的元素即為所求，如果沒有被移除，代表右側沒有比該元素小的元素。
- 建立一個遞增的 Stack，由右向左遍歷，插入當前元素時，位於頂部的元素即為所求，如果 Stack 為空，代表右側沒有比該元素大的元素。

可以統整如下：

類型	Stack 類型	遍歷方向	取值時機
左側/大	遞減	左至右	插入時取頂部值
左側/小	遞增	左至右	插入時取頂部值
右側/大	遞減	左至右	移除時取插入值
右側/大	遞增	右至左	插入時取頂部值
右側/小	遞增	左至右	移除時取插入值
右側/小	遞減	右至左	插入時取頂部值

練習

LeetCode 32. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Example 1:
Input: s = “(()”
Output: 2

Example 2:
Input: s = “)()())”
Output: 4

Example 3:
Input: s = “”
Output: 0

Solution:

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        stk.push(-1);
        int ans = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '(') stk.push(i);
            else{
                stk.pop();
                if(stk.empty()) stk.push(i);
                else ans = max(ans, i - stk.top());
            }
        }
        return ans;
    }
};

Stack 在這裡是用來儲存 上一組成功匹配的括號的尾端 的下標，一開始先 push -1 進去，並且遵循以下邏輯：

輸入為 '(' 則將下標放入 Stack 中。
輸入為 ')' 則 pop Stack 頂端下標，如果：
- Stack 為空：pop 的元素為 上一組成功匹配的括號的尾端 的下標，將此時的下標存入 Stack 中。
- Stack 不為空：成功匹配前一個括號，計算當前最長子字串的長度儲存到 ans 中。

每次位於 Stack 底部的元素都會是 上一組成功匹配的括號的尾端 的下標，如果把它 pop 了就代表當前的子字串匹配完畢，因此要把當前的下標儲存入 Stack 中。

LeetCode 739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]

Solution:

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk;
        vector<int> ans(temperatures.size());
        for(int i = 0; i < temperatures.size(); i++){
            while(!stk.empty() && temperatures[stk.top()] < temperatures[i]){
                ans[stk.top()] = i - stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return ans;
    }
};

這一題是要找元素右側第一個比該元素大的元素，因此建構了一個遞減 Stack，不過 Stack 內部儲存的是對應的下標值，用來計算相隔的天數。

LeetCode 316. Remove Duplicate Letters

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is
the smallest in lexicographical orderamong all possible results.

Example 1:
Input: s = “bcabc”
Output: “abc”

Example 2:
Input: s = “cbacdcbc”
Output: “acdb”

Solution:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<bool> inStk(26, false);
        vector<int> c(26, 0);
        stack<char> stk;
        for(int i = 0; i < s.size(); i++){
            c[s[i] - 'a']++;
        }
        for(int i = 0; i < s.size(); i++){
            if(!inStk[s[i] - 'a']){
                while(!stk.empty() && c[stk.top() - 'a'] > 0 && stk.top() > s[i]){
                    inStk[stk.top() - 'a'] = false;
                    stk.pop();
                }
                stk.push(s[i]);
                inStk[s[i] - 'a'] = true;
            }
            c[s[i] - 'a']--;
        }
        string ans = "";
        while(!stk.empty()){
            ans = stk.top() + ans;
            stk.pop();
        }
        return ans;
    }
};

為了讓 Stack 裡面的元素以最小的字典序儲存，同時又要確保每個字母只出現一次，因此建立了兩個 vector 分別用來儲存 該字母是否已經在 Stack 中 以及 在字串中的出現次數。
遍歷整個字串，如果該字母在 Stack 中，重複判斷頂部元素出現次數是否大於 0 且字母序比該字母大，如果是則移除頂部元素，直到條件不成立時就可以將當前字母放入 Stack 中，並且把出現次數減一。

LeetCode 155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

Example 1:
Input
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]

Solution 1:

class MinStack {
public:
    stack<int> stk;
    stack<int> stkMin;
    MinStack() {
        
    }
    
    void push(int val) {
        stk.push(val);
        if(stkMin.empty() || val <= stkMin.top()) stkMin.push(val);
        return;
    }
    
    void pop() {
        if(stkMin.top() == stk.top()) stkMin.pop();
        stk.pop();
        return;
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return stkMin.top();
    }
};

使用遞減 Stack stkMin 儲存最小值，如果 push 的值小於或等於 stkMin 的頂端值則將其放入，如果在 pop 的時候剛好是移除最小值，則要將 stkMin 的頂端值移除。

Solution 2:

class MinStack {
public:
    stack<int> stk;
    vector<int> v;
    MinStack() {
        
    }
    
    void push(int val) {
        stk.push(val);
        if(v.empty()) v.push_back(val);
        else v.push_back(min(val, v[v.size() - 1]));
        return;
    }
    
    void pop() {
        v.pop_back();
        stk.pop();
        return;
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return v[v.size() - 1];
    }
};

使用 vector 紀錄 Stack 每個位置作為結尾的最小值。

更多關於單調 Stack 的細節可以參考 Monotonic Stack/Deque