一、题目
1、字符串解码（LC 394）
2、最小栈（LC 155）
3、有效的括号（LC 20）
二、题解
1、字符串解码（LC 394）
（1）分析
这道题需要把带方括号和数字的编码字符串进行解码，比如把 3[a] 变成 aaa，这种带有嵌套结构适合用栈来解决，因为遇到括号就要回退到上一层处理，刚好符合栈先进后出的特点。整体思路，用两个栈分别保存数字和字符串，再用一个可变字符串实时保存当前正在拼接的内容。
遍历字符串里的每一个字符时，会遇到四种情况：数字、左括号、右括号、普通字母。如果遇到数字，不能直接保存，因为数字可能是多位数，所以要通过计算把字符转成真正的整数。如果遇到左括号，就说明要进入嵌套了，这时候把当前记录的数字和字符串分别压入对应的栈中，然后重置数字和当前字符串，准备处理括号里的内容。
当遇到右括号时，就代表当前层级的字符串结束了，需要把它按照之前保存的数字重复多次。这时候从数字栈取出要重复的次数，把当前字符串复制对应次数，再从字符串栈取出上一层的内容，把两者拼接起来，继续向上一层返回。如果只是普通字母，直接追加到当前字符串后面就可以，最后返回 res 字符串即可。
（2）解答
class Solution { /* 遇到的字符可能是 "[","]",数字,字母; 数字后面一定有左括号 "[" 遇到 "[" --- 数字放入数字栈、字符串放入字符串栈 遇到 "]" --- 取出数字，复制当前字符，再取出字符栈中的字符拼接当前字符 */ public String decodeString(String s) { Deque<Integer> stack_num = new ArrayDeque<>(); //存放数字的栈 Deque<String> stack_str = new ArrayDeque<>(); //存放字符串的栈 StringBuilder res = new StringBuilder(); int num = 0; //num用来计数 for(char ch : s.toCharArray()){ if(ch >='0' && ch <='9'){ //遇到数字字符，计算数字 num = ch - '0' + num * 10; }else if(ch == '['){ //遇到 "[" stack_num.push(num); //把数字存放在数字栈 stack_str.push(res.toString()); //把字符串存放在字符串栈 num = 0; res = new StringBuilder(); }else if(ch == ']'){ //遇到 "]" Integer count = stack_num.pop(); //取出数字栈的栈顶数字 StringBuilder temp = new StringBuilder(); for(int i = 0; i < count; i++){ //根据数字复制字符串 temp.append(res); } res = new StringBuilder(stack_str.pop() + temp); //与字符栈栈顶元素拼接 }else{ //ch为字母 res.append(ch); } } return res.toString(); } }2、最小栈（LC 155）
（1）分析
这道题要求实现一个栈，同时能在常数时间内获取栈中的最小元素，普通的栈做不到这一点，所以需要改造一下栈的存储结构。不让栈里只保存单个数值，而是保存一个数组，数组里包含两个值，一个是当前入栈的元素本身，另一个是从栈底到当前位置的最小值。
为了避免判断栈空的麻烦，可以在初始化的时候直接放入一个哨兵元素作为栈底，把最小值设为整数最大值，这样后续操作就不用处理边界问题。每次新元素入栈时，最小值都由当前元素和栈顶的最小值比较得出，保证每一个栈位都记录着截至自己位置的最小值。
如此，获取最小值，直接取栈顶数组里记录的最小值即可。出栈、取栈顶的操作和普通栈一样，只是读取数组对应位置的值。此时就实现了正常栈功能和获取最小元素的功能，时间复杂度为O(1)。
（2）解答
class MinStack { private final Deque<int[]> stack = new ArrayDeque<>(); public MinStack() { stack.push(new int[]{0, Integer.MAX_VALUE}); //哨兵栈底 } public void push(int val) { stack.push(new int[]{val, Math.min(val, getMin())}); } public void pop() { stack.pop(); } public int top() { return stack.peek()[0]; //stack.peek()得到的是数组，[0]表示第一个元素val值 } public int getMin() { return stack.peek()[1]; //[1]表示数组第二个元素，草拟稿栈底到当前的最小值 } } //栈中的数组，后一个元素指的是是什么---从栈底到当前位置的最小值 */ /** * 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、有效的括号（LC 20）
（1）分析
判断一个括号字符串是否有效，核心就是左括号必须按顺序闭合，不能交叉，也不能缺少。可以用栈保存所有左括号，再用哈希表存储左右括号的对应关系，方便匹配。
如果字符串长度是奇数，那一定不可能匹配成功，直接返回 false。然后建立左括号到右括号的映射关系，让后续查找更方便。遍历字符串时，遇到左括号就直接压入栈中，遇到右括号就进行匹配检查。
如果遇到右括号时栈已经是空的，说明没有对应的左括号，无效。如果栈不为空，就取出栈顶的左括号，看它对应的右括号和当前字符是否一致，不一致就说明括号不匹配。遍历完成后，如果栈收空的，说明全部匹配了，如果栈不为空，说明字符串无效。
（2）解答
class Solution { public boolean isValid(String s) { if(s.length() % 2 != 0){return false;} //字符数为奇数，不符合 HashMap<Character, Character> map = new HashMap<>(); map.put('(',')'); map.put('{','}'); map.put('[',']'); char[] chs = s.toCharArray(); Deque<Character> stack = new ArrayDeque<>(); for(char ch : chs){ if(map.containsKey(ch)){ //ch是左括号，入栈 stack.push(ch); }else{ if(stack.isEmpty()){return false;} //栈为空，返回false char ch1 = stack.pop(); if(map.get(ch1) != ch){ //ch是右括号，查询与栈中括号是否匹配 return false; } } } return stack.isEmpty(); } } //左括号入栈，右括号消除
 漏洞影响)
