【力扣Hot 100】栈

1. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

题解

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 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 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 <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• 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 <= 105
• 30 <= 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;}
};