用栈解决
class Solution { public boolean find132pattern(int[] nums) { Stack<Integer> stack=new Stack<>(); int[] min=new int[nums.length]; min[0]=nums[0]; for (int i=1;i<nums.length;i++){ min[i] = Math.min(min[i - 1], nums[i]); } for (int i=nums.length-1;i>=0;i--){ while(!stack.isEmpty()&&min[i]>=stack.peek()){ stack.pop(); } if (!stack.isEmpty()&&stack.peek()<nums[i]) return true; stack.push(nums[i]); } return false; } } 括号的分数用栈解决
class Solution { public int scoreOfParentheses(String S) { Stack<Integer> stack=new Stack<>(); stack.push(0); for (int i=0;i<S.length();i++){ char c=S.charAt(i); if (c=='('){ stack.push(0); }else { int a=stack.pop(); int b=stack.pop(); stack.push(b+Math.max(a*2,1)); } } return stack.peek(); } }不用栈解决
class Solution { public int scoreOfParentheses(String S) { int score=0; int layer=0; for (int i=0;i<S.length();i++){ char c=S.charAt(i); if (c=='('){ layer++; }else { layer--; if (S.charAt(i-1)=='('){ score+=1<<layer; } } } return score; } } 二叉树的层次遍历 由底向上，从左到右 class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res=new ArrayList<>(); if (root==null){ return res; } Stack<Integer> s=new Stack<>(); Stack<Integer> sh=new Stack<>(); Queue<TreeNode> queue=new LinkedList<>(); Queue<Integer> height=new LinkedList<>(); queue.offer(root); height.offer(1); while(!queue.isEmpty() && !height.isEmpty()){ TreeNode p=queue.poll(); int h=height.poll(); s.push(p.val); sh.push(h); if (p.right!=null){ queue.offer(p.right); height.offer(h+1); } if (p.left!=null){ queue.offer(p.left); height.offer(h+1); } } for (int h=sh.peek();h>0;h--){ List<Integer> tmp=new ArrayList<>(); while (!sh.isEmpty()&&sh.peek()==h){ tmp.add(s.pop()); sh.pop(); } res.add(tmp); } return res; } } 反转每对括号间的子串 class Solution { public String reverseParentheses(String s) { StringBuilder sb=new StringBuilder(); char[] chars = s.toCharArray(); Stack<Integer> stack=new Stack<>(); for (int i=0;i<chars.length;i++){ if (chars[i]=='('){ stack.push(i); } if (chars[i]==')'){ Integer start = stack.pop(); reverse(chars,start+1,i-1); } } for (int i=0;i<chars.length;i++){ if (chars[i]!='('&&chars[i]!=')'){ sb.append(chars[i]); } } return sb.toString(); } public void reverse(char[] chars,int start,int end){ while (start<end){ char tmp=chars[start]; chars[start]=chars[end]; chars[end]=tmp; start++;end--; } } } 移掉k位数字使剩下数字最小（402题） 主要思想：遍历字符串中的每一位，使栈中始终维持栈顶元素最大，否则弹出。 class Solution { public String removeKdigits(String num, int k) { Stack<Integer> stack=new Stack<>(); char[] chars=num.toCharArray(); int count=0; for (char c:chars){ int cha=c-'0'; while (!stack.isEmpty()&&cha<stack.peek() && count<k){ stack.pop(); count++; } stack.push(cha); } while (count<k){ stack.pop(); count++; } Stack<Integer> stack1=new Stack<>(); while (!stack.isEmpty()){ stack1.push(stack.pop()); } while (!stack1.isEmpty()&&stack1.peek()==0){ stack1.pop(); } if (stack1.isEmpty()){ return String.valueOf(0); } StringBuilder sb=new StringBuilder(); while (!stack1.isEmpty()){ sb.append(stack1.pop()); } return sb.toString(); } } 去除重复字母（316题） class Solution { public String removeDuplicateLetters(String s) { Stack<Character> stack=new Stack<>(); Stack<Integer> IndexStack=new Stack<>(); Map<Character,Integer> endIndex=new HashMap<>(); for (int i=0;i<s.length();i++){ endIndex.put(s.charAt(i),i); } for (int i=0;i<s.length();i++){ char ch=s.charAt(i); if (!stack.contains(ch)){ while (!stack.isEmpty() && ch<stack.peek() && endIndex.get(stack.peek())>i){ stack.pop(); } stack.push(ch); IndexStack.push(i); } } StringBuilder sb=new StringBuilder(); while (!stack.isEmpty()){ sb.append(stack.pop()); } return sb.reverse().toString(); } } 不同字符的最小子序列（1081题） 和上一题完全相同。拼接最大数用到了上面第10题的思想，还用到了合并的思想。将问题分解。
class Solution { public int[] maxNumber(int[] nums1, int[] nums2, int k) { int[] res=null; for (int i=0;i<=k;i++){ if (i>nums1.length || k-i>nums2.length){ continue; } int[] a = subMax(nums1, i); int[] b = subMax(nums2, k - i); int[] merge = merge(a, b); if (res==null){ res=merge; }else { if (compare(merge,res)){ res=merge; } } } return res; } //按顺序取k个数让结果最大 public int[] subMax(int[] nums, int n) { //要删除的个数 int k=nums.length-n; //返回的结果 int[] res=new int[n]; Stack<Integer> stack=new Stack<>(); int count=0; for (int i:nums){ while (!stack.isEmpty()&&i>stack.peek() && count<k){ stack.pop(); count++; } stack.push(i); } while (count<k){ stack.pop(); count++; } for (int i=res.length-1;i>=0;i--){ res[i]=stack.pop(); } return res; } //合并数组 public int[] merge(int[] a,int[] b){ if (a.length==0) return b; if (b.length==0) return a; int[] res=new int[a.length+b.length]; int i=0,j=0; for (int index=0;index<res.length;index++){ if(compare(Arrays.copyOfRange(a, i, a.length),Arrays.copyOfRange(b, j, b.length))){ res[index] = a[i++]; } else{ res[index] = b[j++]; } } return res; } //判断数组a是否大于等于数组b public boolean compare(int[] a,int[] b){ int n=Math.min(a.length,b.length); for (int i=0;i<n;i++){ if (a[i]>b[i]){ return true; } if (a[i]<b[i]){ return false; } } return a.length-b.length>0; } } 栈的压入、弹出顺序（剑指offer 31题） class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { if (pushed.length!=popped.length){ return false; } Stack<Integer> stack=new Stack<>(); int index=0; for (int value : pushed) { stack.push(value); while (!stack.isEmpty() && popped[index]==stack.peek()) { index++; stack.pop(); } } return index==popped.length; } }