概述

什么情况使用栈？

1. 利用栈的后进先出性质。
2. 输入：数组，输出：与数组下标和元素都相关。而且栈中构成一定的顺序比如递增、递减，如果不满足则出栈进行计算。

   需要注意的情况

3. 搞清楚什么时候需要入栈、出栈
4. 搞清楚栈中应该放元素or下标
5. 什么时候更新结果

42和84一样的题就是求最大/求和的区别。他们两个和32题很像，相同点：

• 都是求最大值，结果范围不确定。
• 到达某个点之后满足条件对栈顶出栈进行操作，更新最大值。
• 都是通过栈保存数组下标，一遍求范围或宽度。
• 遍历过程中栈会出栈导致下标不连续从而求出范围。

  不同点：

• 32题只是求一维的范围，而84题求下标范围和对应数组中值的乘积，属于二维。然而时间复杂度都是O(n)。
• 32题中入栈操作是遍历到’(‘或者’)’但是栈中为空或栈顶不是’(‘时，而84题每次都会入栈。
• 出栈条件不同，32题为新元素为’)’且栈顶为’(‘，if语句；而84题为新元素的高度小于栈顶，语句为while。

题目

150. Evaluate Reverse Polish Notation

• 描述：在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法

  Input: ["2", "1", "+", "3", "*"]
  Output: 9
  Explanation: ((2 + 1) * 3) = 9
  

• 思路：对vector从左到右进行遍历，每次遇到数字就放入栈中，每次遇到运算符就从栈中取出两个数字并使用该运算符对这两个数字进行运算，结果再放入栈中。最后栈中应该只剩1个元素，该元素就是结果。
• 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

• 描述：包含三种括号，是否满足左开右闭。 ``` Input: “()[]{}” Output: true

Input: “(]” Output: false

* 思路：使用栈保存左边的，出现右边时进行判断若栈顶和该右括号恰好抵消则出栈。
* Time:O(n) Space:O(n)

[//]: # ()
```c++
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

• 描述：一个只包含左括号’(‘和右括号’)’的string中，求满足左开右闭的最大长度

  Input: ")()())"
  Output: 4
  Explanation: The longest valid parentheses substring is "()()"
  

• 思路：使用栈记录每个左括号和未命中的右括号的位置，每次遇到可以命中的右括号则取出栈顶并更新最大长度。
• 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

• 描述：直方图中找出面积最大的长方形

  Input: [2,1,5,6,2,3]
  Output: 10
  

• 思路：数组中所有值都会入栈，作为高度h。而宽度，由比h小的两个下标给出。

  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() && heights[pos_stack.top()] >= 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

• 描述：几个柱状体的盛水大小

  Input: [0,1,0,2,1,0,1,3,2,1,2,1]
  Output: 6
  

• 思路：最优肯定是使用左右记录最大高度。使用栈也可以做，便于理解。 入栈：只有<=栈顶的元素才入栈。出栈：当元素>栈顶时，栈顶做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;
  }