20. 有效的括号 - 力扣LeetCodeclass Solution { public boolean isValid(String s) { DequeCharacter qu new LinkedList(); if(s.length()0){ return true; } for(int i0;i s.length();i){ if(!qu.isEmpty() qu.peek() ( s.charAt(i) )){ qu.pop(); continue; } if(!qu.isEmpty() qu.peek() [ s.charAt(i) ]){ qu.pop(); continue; } if(!qu.isEmpty() qu.peek() { s.charAt(i) }){ qu.pop(); continue; } qu.push(s.charAt(i)); } if(qu.size()0){ return false; } return true; } }155. 最小栈 - 力扣LeetCode双栈同时压入一个最小栈栈顶维持到当前为止主栈里所有元素的最小值class MinStack { DequeInteger ds new LinkedList(); DequeInteger ms new LinkedList(); public MinStack() { } public void push(int value) { ds.push(value); ms.push(ms.isEmpty() ? value :Math.min(ms.peek(),value)); } public void pop() { ds.pop(); ms.pop(); } public int top() { return ds.peek(); } public int getMin() { return ms.peek(); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj new MinStack(); * obj.push(value); * obj.pop(); * int param_3 obj.top(); * int param_4 obj.getMin(); */394. 字符串解码 - 力扣LeetCode不会写括号把字符串切成一层一层的嵌套结构。每一层进入时要记住“外层状态”每层结束时把本层结果拼回外层。具体来说遇到[→ 进入新的一层把外层状态压栈。遇到]→ 本层结束弹出外层状态把本层结果重复k次拼到外层后面当前层变回外层。遇到数字 → 累加到curNum作为下一个[的重复次数。遇到字母 → 拼到当前层字符串。栈的作用保存每一层进入括号之前的外层状态因为嵌套层数不确定不能用固定变量。最不容易理解的curLeftStr阶段curLeftStr代表什么遇到[之前当前层已经拼好的字符串即将作为外层字符串压栈遇到[之后括号内部正在解码的内容遇到]之后本层合并完成后的结果同时当前层变回外层class Solution { public String decodeString(String s) { DequeInteger count new LinkedList(); DequeStringBuilder str new LinkedList(); int curNum0; StringBuilder curLeftStr new StringBuilder(); for(int i0;is.length();i){ Character c s.charAt(i); if(c 0 c 9){ curNum curNum * 10 (c-0); }else if(c [){ count.push(curNum); str.push(curLeftStr); curNum0; curLeftStrnew StringBuilder(); }else if(c]){ int popNum count.pop(); StringBuilder popStr str.pop(); for(int j0;jpopNum;j){ popStr.append(curLeftStr); } curLeftStrpopStr; }else{ curLeftStr.append(c); } } return curLeftStr.toString(); } }739. 每日温度 - 力扣LeetCode单调递减栈下标本身从栈底到栈顶是递增的因为按遍历顺序入栈后入栈的下标更大。下标对应的温度从栈底到栈顶是递减的。所以栈的性质是下标递增温度递减。栈内下标递增、对应温度递减。遍历到新的下标i时如果temperatures[i]大于栈顶下标对应的温度就弹出栈顶栈顶下标prev的右边第一个更高温度就是i等待天数为i - prev。继续比较新的栈顶直到栈空或temperatures[i] 栈顶温度然后把i入栈。class Solution { public int[] dailyTemperatures(int[] temperatures) { int []resnew int[temperatures.length]; DequeInteger sk new LinkedList(); for(int i 0;itemperatures.length;i){ while(!sk.isEmpty() temperatures[i]temperatures[sk.peek()]){ int prev sk.pop(); res[prev] i - prev; } sk.push(i); } return res; } }84. 柱状图中最大的矩形 - 力扣LeetCode