栈的基本算法

1.单调栈

1) 每日温度

public static int[] dailyTemperatures(int[] temperatures) {int len = temperatures.length;int [] ans = new int [len];Deque<Integer> stack = new LinkedList<Integer>();for(int i = 0; i < len; i++){int temperature = temperatures[i];while(!stack.isEmpty() &&  temperature > temperatures[stack.peek()]){int prevIndex = stack.pop();ans[prevIndex] = i - prevIndex;}stack.push(i);}return ans;}

2. 计算器，括号匹配，最大最小问题

 2）字符编码

static  int i = 0;public String decodeString(String s){LinkedList<String> stack = new LinkedList<>();Character cur;while(i < s.length()){cur = s.charAt(i);if(Character.isDigit(cur)){stack.addLast(getDigits(s));}else if(Character.isLetter(s.charAt(i)) || cur == '['){stack.addLast(String.valueOf(s.charAt(i++)));}else {i++;LinkedList <String> sub = new LinkedList();while(!"[".equals(stack.peekLast())){sub.addLast(stack.removeLast());}Collections.reverse(sub);stack.removeLast();Integer count = Integer.parseInt(stack.removeLast());StringBuilder sb = new StringBuilder();String s1 = getString(sub);while(count > 0){sb.append(s1);count--;}stack.addLast(sb.toString());}}return getString(stack);}public String getString(LinkedList<String> list){StringBuffer sb = new StringBuffer();for(String s: list){sb = sb.append(s);}return sb.toString();}public String getDigits(String s){StringBuffer sb = new StringBuffer();while(Character.isDigit(s.charAt(i))){sb.append(s.charAt(i++));}return sb.toString();}