什么情况使用栈？
- 利用栈的后进先出性质。
- 输入：数组，输出：与数组下标和元素都相关。而且栈中构成一定的顺序比如递增、递减，如果不满足则出栈进行计算。
需要注意的情况
- 搞清楚什么时候需要入栈、出栈
- 搞清楚栈中应该放元素or下标
- 什么时候更新结果
42和84一样的题就是求最大/求和的区别。他们2个和32题很像，相同点：
- 都是求最大值，结果范围不确定。
- 到达某个点之后满足条件对栈顶出栈进行操作，更新最大值。
- 都是通过栈保存数组下标，一遍求范围或宽度。
- 遍历过程中栈会出栈导致下标不连续从而求出范围。
不同点：
- 32题只是求一维的范围，而84题求下标范围和对应数组中值的乘积，属于二维。然而时间复杂度都是O(n)。
- 32题中入栈操作是遍历到'('或者')'但是栈中为空或栈顶不是'('时，而84题每次都会入栈。
- 出栈条件不同，32题为新元素为')'且栈顶为'('，if语句；而84题为新元素的高度小于栈顶，语句为while。
描述：在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法
思路：对vector从左到右进行遍历，每次遇到数字就放入栈中，每次遇到运算符就从栈中取出2个数字并使用该运算符对这2个数字进行运算，结果再放入栈中。最后栈中应该只剩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();
}
描述：包含三种括号，是否满足左开右闭。
思路：使用栈保存左边的，出现右边时进行判断若栈顶和该右括号恰好抵消则出栈。
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();
}
描述：一个只包含左括号'('和右括号')'的string中，求满足左开右闭的最大长度
思路：使用栈记录每个左括号和未命中的右括号的位置，每次遇到可以命中的右括号则取出栈顶并更新最大长度。
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;
}
描述：直方图中找出面积最大的长方形
思路：将vector的下标存放在栈中。栈顶存放的下标是栈中最高的，当当前高度比栈顶的低时，找出栈顶高度适合的宽度（比栈顶低下标，不一定连续），这样就保证了缺失部分都是>=栈顶高度的。栈中保存下标对应高度是递增的，中间缺失部分为高于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;
}
描述：几个柱状体的盛水大小
思路：最优肯定是使用左右记录最大高度。使用栈也可以做，便于理解。 入栈：只有<=栈顶的元素才入栈。出栈：当元素>栈顶时，栈顶做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;
}
