【力扣Hot 100】栈
1. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
**输入：**s = “()”
**输出：**true
示例 2：
**输入：**s = “()[]{}”
**输出：**true
示例 3：
**输入：**s = “(]”
**输出：**false
示例 4：
**输入：**s = “([])”
**输出：**true
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
题解
class Solution {
public:bool isValid(string s) {int n = s.size();if(n % 2 == 1) return false;unordered_map<char, char> pairs = {{')', '('},{']', '['},{'}', '{'}};stack<char> stk;for(char ch : s) {if(pairs.count(ch)) {if(stk.empty() || stk.top() != pairs[ch]) return false;stk.pop();}else {stk.push(ch);}}return stk.empty();}
};
2. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出：
[null,null,null,null,-3,null,0,-2]解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.提示：
231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
题解
维护两个栈，一个 stk 表示普通的栈，一个 minstk 表示普通栈的每个栈顶对应的最小值。
示例：
普通栈： [ a, b, c, d
minstk： [ a, min(a, b), min(c, min(a,b)), min(d, min(c, min(a,b)))
class MinStack {
public:stack<int> stk;stack<int> minstk;MinStack() {minstk.push(INT_MAX); }void push(int val) {minstk.push(min(minstk.top(), val));stk.push(val);}void pop() {minstk.pop();stk.pop();}int top() {return stk.top();}int getMin() {return minstk.top();}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/
3. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"提示：
1 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
题解
用两个栈，一个存数字，一个存字符串
用一个数字表示当前的次数，一个字符串表示当前的字符串
当遇到“[”，说明即将进入下一级，所以要把数字和字符串都存档一下，存入栈中。
当遇到“]”，说明结束了一个层级，要把数字栈的数字nums.top()拿出来，把字符串栈的字符串strs.top()拿出来，把当前字符串重复nums.top()次，并拼接到strs.top()后面，作为新的当前字符串。
class Solution {
public:string decodeString(string s) {stack<int> nums;stack<string> strs;string str = "";int num = 0;int n = s.size();for(int i = 0; i < s.size(); i ++ ) {if(s[i] >= '0' && s[i] <= '9') {num = num * 10 + s[i] - '0';}else if(s[i] >= 'a' && s[i] <= 'z') {str += s[i];} else if(s[i] == '[') {nums.push(num);num = 0;strs.push(str);str = "";}else {int times = nums.top();nums.pop();for(int j = 0; j < times; j ++ ) {strs.top() += str;}str = strs.top();strs.pop();}}return str;}
};
4, 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入:temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]示例 3:
输入: temperatures = [30,60,90]
输出:[1,1,0]
提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
题解
使用单调栈来解决。
维护一个单调栈，存储温度的下标，并使得栈中从栈底到栈顶温度依次递减。
遍历温度数组，每当当前温度大于栈顶元素的温度，那么不符合单调递减栈，所以要把栈中的元素依次弹出，并更新对应的ans数组。最后再插入当前温度的下标。
（说不清楚，看代码吧。。）
class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n, 0);stack<int> stk;for(int i = 0; i < n; i ++ ) {while(!stk.empty() && temperatures[i] > temperatures[stk.top()]) {ans[stk.top()] = i - stk.top();stk.pop();}stk.push(i);}return ans;}
};