什么情況使用棧？

1. 利用棧的后進(jìn)先出性質(zhì)。
2. 輸入：數(shù)組，輸出：與數(shù)組下標(biāo)和元素都相關(guān)。而且棧中構(gòu)成一定的順序比如遞增、遞減，如果不滿足則出棧進(jìn)行計(jì)算。

需要注意的情況

1. 搞清楚什么時(shí)候需要入棧、出棧
2. 搞清楚棧中應(yīng)該放元素or下標(biāo)
3. 什么時(shí)候更新結(jié)果

42和84一樣的題就是求最大/求和的區(qū)別。他們2個(gè)和32題很像，相同點(diǎn)：

1. 都是求最大值，結(jié)果范圍不確定。
2. 到達(dá)某個(gè)點(diǎn)之后滿足條件對(duì)棧頂出棧進(jìn)行操作，更新最大值。
3. 都是通過(guò)棧保存數(shù)組下標(biāo)，一遍求范圍或?qū)挾取?/li>
4. 遍歷過(guò)程中棧會(huì)出棧導(dǎo)致下標(biāo)不連續(xù)從而求出范圍。

不同點(diǎn)：

1. 32題只是求一維的范圍，而84題求下標(biāo)范圍和對(duì)應(yīng)數(shù)組中值的乘積，屬于二維。然而時(shí)間復(fù)雜度都是O(n)。
2. 32題中入棧操作是遍歷到'('或者')'但是棧中為空或棧頂不是'('時(shí)，而84題每次都會(huì)入棧。
3. 出棧條件不同，32題為新元素為')'且棧頂為'('，if語(yǔ)句；而84題為新元素的高度小于棧頂，語(yǔ)句為while。

150. Evaluate Reverse Polish Notation

描述：在逆波蘭記法中，所有操作符置于操作數(shù)的后面，因此也被稱為后綴表示法

思路：對(duì)vector從左到右進(jìn)行遍歷，每次遇到數(shù)字就放入棧中，每次遇到運(yùn)算符就從棧中取出2個(gè)數(shù)字并使用該運(yùn)算符對(duì)這2個(gè)數(shù)字進(jìn)行運(yùn)算，結(jié)果再放入棧中。最后棧中應(yīng)該只剩1個(gè)元素，該元素就是結(jié)果。

Time:O(n) Space:O(n)

int evalRPN(vector<string>& tokens) {
    stack<int> operands;
    set<string> operator_set = {"+", "-", "*", "/"};
    
    for (auto to:tokens) {
        if (operator_set.find(to) != operator_set.end()) {
            int right = operands.top();
            operands.pop();
            int left = operands.top();
            operands.pop();
            if (to == "+") operands.push(left + right);
            else if (to == "-") operands.push(left - right);
            else if (to == "*") operands.push(left * right);
            else if (to == "/") operands.push(left / right);
        } else {
            operands.push(stoi(to));
        }
    }
    
    return operands.top();
}

20. Valid Parentheses

描述：包含三種括號(hào)，是否滿足左開右閉。

思路：使用棧保存左邊的，出現(xiàn)右邊時(shí)進(jìn)行判斷若棧頂和該右括號(hào)恰好抵消則出棧。

Time:O(n) Space:O(n)

bool isValid(string s) {
    stack<char> parentheses;
    unordered_map<char, char> left2right = {{'\(', '\)'}, {'\{', '\}'}, {'\[', '\]'}};
    for (char c:s) {
        if (c == '\(' || c == '\{' || c == '\[') {
            parentheses.push(c);
        } else if (!parentheses.empty() && c == left2right[parentheses.top()]) {
            parentheses.pop();
        } else{
            return false;
        }
    }
    return parentheses.empty();
}

32. Longest Valid Parentheses

描述：一個(gè)只包含左括號(hào)'('和右括號(hào)')'的string中，求滿足左開右閉的最大長(zhǎng)度

思路：使用棧記錄每個(gè)左括號(hào)和未命中的右括號(hào)的位置，每次遇到可以命中的右括號(hào)則取出棧頂并更新最大長(zhǎng)度。

Time:O(n) Space:O(n)

int longestValidParentheses(string s) {
    stack<int> s_pos;
    int res = 0;
    for (auto i = 0; i < s.size(); ++i) {
        if (!s_pos.empty() && s[i] == '\)' && s[s_pos.top()] == '\(') {
            s_pos.pop();
            int last_pos = -1;
            if (!s_pos.empty()) last_pos = s_pos.top();
            res = max(res, i - last_pos);
        } else {
            s_pos.push(i);
        }
    }
    return res;
}

84. Largest Rectangle in Histogram

描述：直方圖中找出面積最大的長(zhǎng)方形

思路：將vector的下標(biāo)存放在棧中。棧頂存放的下標(biāo)是棧中最高的，當(dāng)當(dāng)前高度比棧頂?shù)牡蜁r(shí)，找出棧頂高度適合的寬度（比棧頂?shù)拖聵?biāo)，不一定連續(xù)），這樣就保證了缺失部分都是>=棧頂高度的。棧中保存下標(biāo)對(duì)應(yīng)高度是遞增的，中間缺失部分為高于2邊的情況。

int largestRectangleArea(vector<int>& heights) {
    int res = 0;
    stack<int> pos_stack;
    heights.push_back(0);
    
    for (auto i = 0; i < heights.size(); ++i) {
        while (!pos_stack.empty() && 0. >= heights[i]) {
            int h = heights[pos_stack.top()];
            pos_stack.pop();
            
            int last_pos = -1;
            if (!pos_stack.empty()) last_pos = pos_stack.top();
            res = max(res, h*(i - last_pos - 1));
        }
        pos_stack.push(i);
    }
    
    return res;
}

42. Trapping Rain Water

描述：幾個(gè)柱狀體的盛水大小

思路：最優(yōu)肯定是使用左右記錄最大高度。使用棧也可以做，便于理解。 入棧：只有<=棧頂?shù)脑夭湃霔！３鰲＃寒?dāng)元素>棧頂時(shí)，棧頂做bottom并出棧，比較該棧頂2遍高度選取小的與bottom做差并求出面積。

Time:O(n) Space:O(n)

int trap(vector<int>& height) {
    if (height.size() < 3) return 0;
    int res = 0;
    stack<int> height_pos;
    
    for (int i = 0; i < height.size(); ++i) {
        while (!height_pos.empty() && height[i] > height[height_pos.top()]) {
            int bottom = height[height_pos.top()];
            height_pos.pop();
            
            if (!height_pos.empty()) {
                res += (min(height[height_pos.top()], height[i]) - bottom)*(i - height_pos.top() - 1);
            }
        } 
        height_pos.push(i);
    }
    return res;
}