算法题（栈）

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