栈

1.有效的括号

有效的括号
这道题肯定是利用了栈先入后出的特性。有以下几种情况
如果当前元素是左括号则push进栈不弹出；
如果当前元素是右括号则弹出栈中前一个元素，并判断是否与当前元素匹配。

class Solution {
public:bool isValid(string s) {stack<char> ans;for (auto s1: s) {if (s1 == '(' || s1 == '{' || s1 == '[') {ans.push(s1);} else {if (ans.empty()) return false;auto tmp = ans.top();//注意这里，s1是右括号if ((s1 == ')' && tmp != '(') || (s1 == '}' && tmp != '{' ) || (s1 == ']' && tmp != '['))return false;ans.pop();}}return ans.empty();}
};

2.最小栈

最小栈
观察题目要求：实现 MinStack 类。实际是想用两个stack类实现MinStack类。难点就在于如何获取最小元素，一个栈正常push元素，另一个栈存放当前栈中的最小元素。

void push(int val) 将元素val推入堆栈----> stack push(val) 以及 stack_min.push(min(val, stack_min.top()))
void pop() 删除堆栈顶部的元素----> stack.pop() stack_min.pop()
int top() 获取堆栈顶部的元素-----> stack top()
int getMin() 获取堆栈中的最小元素----> stack1.top()
MinStack() 初始化堆栈对象----> stack1.push(INT_MAX)

class MinStack {
public:stack<int> a;stack<int> a_min;MinStack() {a_min.push(INT_MAX);}void push(int val) {a.push(val);a_min.push(min(val, a_min.top()));}void pop() {a.pop();a_min.pop();}int top() {return a.top();}int getMin() {return a_min.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.字符串解码

其实与括号的题目有点类似，用两个栈，分别为数字栈字母栈。

• 如果是数字入数字栈，字母和左括号就一直入字母栈；

• 如果遇到了右括号就从字母栈pop, 直到遇到左括号为止，获取到需要重复的子串tmp，注意这里的tmp需要reverse；
  再从数字栈pop一个数字，即为需要重复的次数。

• 把（重复次数 * 重复字母）的子串再次入字母栈参与下一层重复

• 最终的结果还需要reverse

class Solution {
public:string decodeString(string s) {string ans;stack<char> stk_s;stack<int> stk_n;int num = 0;for (auto ch: s) {if (ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';} else if (ch == '[') {//把当前子串重复的数字入栈stk_n.push(num);//重新计算下一个子串的重复数字num = 0;stk_s.push(ch);} else if (ch == ']') {//获取需要重复的字符string tmp;//直到遇到'['为止while (stk_s.top() != '[') {tmp += stk_s.top();stk_s.pop();}//弹出'['stk_s.pop();//栈先入后出，所以需要reversereverse(tmp.begin(),tmp.end());//获取重复次数int n = stk_n.top();stk_n.pop();//根据倍数把字母再push回去while (n--) {for (auto ch1: tmp) {stk_s.push(ch1);}}} else {//字母，入栈stk_s.push(ch);}}//栈中元素给stringwhile(stk_s.size()){ans += stk_s.top();stk_s.pop();}reverse(ans.begin(),ans.end());return ans;}
};