Leetcode 3.25

栈

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();
                //栈先入后出，所以需要reverse
                reverse(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);
            }
        }
        //栈中元素给string
        while(stk_s.size()){
            ans += stk_s.top();
            stk_s.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};