1047. 删除字符串中的所有相邻重复项(简单)

class Solution {public String removeDuplicates(String s) {Stack<Character> sta = new Stack<>();for(int i=0;i<s.length();i++){char tp = s.charAt(i);if(!sta.isEmpty()&&tp==sta.peek()){sta.pop();continue;}sta.push(tp);}String res = "";while(!sta.isEmpty()){res = sta.pop()+res;}return res;}
}

150. 逆波兰表达式求值(中等)

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> sta = new Stack<>();for(int i=0;i<tokens.length;i++){if(tokens[i].equals("+")||tokens[i].equals("-")||tokens[i].equals("/")||tokens[i].equals("*")){int b = sta.pop();int a = sta.pop();sta.push(calculate(a,b,tokens[i]));}else {sta.push(Integer.parseInt(tokens[i]));}}return sta.pop();}int calculate(int a,int b,String op){if(op.equals("/"))return a/b;else if(op.equals("+"))return a+b;else if(op.equals("-"))return a-b;else return a*b;}
}

239. 滑动窗口最大值（困难）

思路：1.单调队列 2.堆+集合

//	单调队列
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {MonQueue mque = new MonQueue();int len = nums.length;int res[] = new int[len-k+1];for(int i=0;i<len;i++){if(i>=k&&mque.peek()==nums[i-k])mque.poll();mque.add(nums[i]);if(i>=k-1){res[i-k+1] = mque.peek();}}return res;}//	单调队列class MonQueue{Deque<Integer> deque;public MonQueue(){deque = new LinkedList<>();}public void add(int num){while(!deque.isEmpty()&&deque.getLast()<num){deque.removeLast();}deque.add(num);}public int poll(){return deque.poll();}public int peek(){return deque.peek();}}
}

//	堆+集合
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Map<Integer,Integer> iset = new HashMap<>();Queue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());int len = nums.length;int res[] = new int[len-k+1];for(int i=0;i<len;i++){if(i>=k){int cnt = iset.get(nums[i-k]);if(--cnt<=0)iset.remove(nums[i-k]);else iset.put(nums[i-k],cnt);}int cnt = 0;if(iset.containsKey(nums[i]))cnt = iset.get(nums[i]);iset.put(nums[i],cnt+1);heap.add(nums[i]);if(i>=k-1){while(!iset.containsKey(heap.peek())){heap.poll();}res[i-k+1] = heap.peek();}}return res;}
}

单调队列

//	单调队列class MonQueue{Deque<Integer> deque;public MonQueue(){deque = new LinkedList<>();}public void add(int num){while(!deque.isEmpty()&&deque.getLast()<num){deque.removeLast();}deque.add(num);}public int poll(){return deque.poll();}public int peek(){return deque.peek();}}