【力扣Hot100】栈

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, 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 <= 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; } };