堆，栈，队列题目总结

栈

栈相关题目一般是模拟过程，本身结构不复杂，难点在于你要想的到用栈。

用栈进行模拟直接可以解决，很容易想到题目：

                              . - 力扣（LeetCode）-删除字符串中所有的相邻重复项：利用栈做一下模拟即可。可以使用现成的栈结构，也可以直接在字符串上通过指针模拟整个入栈出栈判断删除的操作：

//使用String直接模拟一个栈，结果直接就是返回，不用进行转化StringBuffer dest = new StringBuffer();int i = 0;//字符串s的遍历指针int j = -1;//dest的标记指针while(i < s.length()) {if(j < 0 || dest.charAt(j) != s.charAt(i)){dest.append(s.charAt(i));j ++;}else{dest.deleteCharAt(j --);}i ++;}return dest.toString();}

                        . - 力扣（LeetCode）同理。直接用栈模拟解决；或者用指针在字符串上模拟栈解决

                       . - 力扣（LeetCode）出栈序列问题，很好联想到到用栈解决。

                         有效括号序列_牛客题霸_牛客网  经典括号匹配问题

需要绕一点弯子不好直接想到：

*****. - 力扣（LeetCode  自己模拟出一个计算器

思路：维护一个字符变量cur表示当前运算符（加减乘除），初始值是+。遍历字符串，遇到数字进行判断：cur是 + 直接将数字入栈；cur 是 - 将数字相反数入栈；cur 是乘法将栈顶元素出栈然后相乘结果入栈；cur是除法将栈顶元素出栈相除结果入栈。    遇到运算符就更新字符变量cur；

此时遍历完字符串后已经将乘法除法进行计算结果入栈，减法转化成加法。所以把栈里的元素相加即可得到结果

//字符串转数字while(i < len && s.charAt(i) <= '9' && s.charAt(i) >= '0') {num = num * 10 + (s.charAt(i) - '0');i ++;
}

. - 力扣（LeetCode）字符串解码 ： 利用栈执行模拟过程。但是这个模拟过程比较绕，

核心就是什么时候字符串直接入栈，什么时候需要拼接到栈顶，要满足嵌套关系。当字符为'['时， [  跟着的字符串需要单独重复，所以直接入栈；不在 [  之后的字符串拼接到栈顶（所以在初始化站的时候要初始一个空数据防止报错）。遇到 ] 则弹出重复之后拼接到栈顶。

大概流程如下：

{Stack<StringBuffer> stack = new Stack<>();//字符串栈Stack<Integer> nums = new Stack<>();//重复次数栈while(i < s.length()) {if(s.charAt(i) == '[') { // [ 将后面的字符串直接入栈}else if(s.charAt(i) == ']'){//将栈顶元素弹出并重复之后拼接到栈顶} else if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {//提取数字加入到数字栈}else{//如果字符串之前没有跟着[，直接拼接到栈顶}}return stack.pop().toString();
}

直接说明使用栈进行操作：

用两个栈实现队列_牛客题霸_牛客网     ：

    Stack<Integer> stack1 = new Stack<Integer>();//push栈Stack<Integer> stack2 = new Stack<Integer>();//pop栈public void push(int node) {stack1.add(node);}public int pop() {if(!stack2.isEmpty()) {//pop栈不为空直接出return stack2.pop();}else if(! stack1.isEmpty()){ //pop栈为空，push栈不为空将push栈移到popwhile(!stack1.isEmpty()) {stack2.add(stack1.pop());}return stack2.pop();}else {return -1;}}

包含min函数的栈_牛客题霸_牛客网   实现一个栈，包含一个返回最小值的min函数，要求为O1时间复杂度。解法：针对最小值维护一个栈：入栈的数小于等于最小值栈顶元素，入栈；出栈的元素等于最小值栈顶元素，最小值栈也出栈。 注意这里要与equals比较，常识但很容易被忽略。

堆

最大（最小）k个数，第k大（第k小）的数  这类题目

最小的k个数/第k小 建大根堆，最大的k个数/第k大 建小根堆

最小的K个数_牛客题霸_牛客网  ：建大小为K的大根堆，遍历数组，堆不满k直接放，满了跟堆顶比较，比堆顶小弹出堆顶放此元素；比堆顶大不做操作。

寻找第K大_牛客题霸_牛客网：建大小为K的小根堆，遍历数组，堆不满k直接放，满了根堆顶比较，比堆顶大堆顶弹出放这个元素；比堆顶小不做操作

. - 力扣（LeetCode）前k个高频单词：1：hashMap统计出现频率  2：建堆比较：这里涉及到俩种堆比较逻辑：需要判断使用比较器：

PriorityQueue<Pair<String,Integer>> queue = new PriorityQueue<>((a,b) -> {if(a.getValue().equals(b.getValue())) {//调用String的compareTo方法进行字典序比较，注意这里是字典序降序return b.getKey().compareTo(a.getKey());}else {//出现次数比较//注意这里大根堆和小根堆对应的写法return a.getValue() - b.getValue();}});

小技巧：这里比较内容是个键值对，可以使用Pair使代码更简洁

         //确定前k个高频单词for(Map.Entry<String,Integer> entry : hash.entrySet()) {queue.offer(new Pair<>(entry.getKey(),entry.getValue()));if(queue.size() > k) queue.poll();}

手写堆

//规定根节点的下标是0，则叶子节点与父节点的关系为：父节点下标 = (叶子节点下标 - 1) / 2private static int[] array;private int size = 0;public PriorityQueue_shousi(int[] nums) {if(nums == null) array = new int[10];else  {array = nums;size = nums.length;}}//建堆过程//在建堆阶段，一定是从下往上逐步建立规则的过程,所以从下往上对每个节点进行向下调整private void buildPriorityQueue() {int start = size - 1;//最后一个节点下标while(start >= 0) {shiftDown(start);start --;}}//添加元素，向上调整public void add(int val) {if(size == array.length) expansion();size ++;array[size - 1] =  val;shiftup(size - 1);}//出堆顶元素：与最后一个元素调换位置，size -- ，堆顶元素向下调整public int poll() {int dest = array[0];swap(0 , size - 1);size --;shiftDown(0);return dest;}//向下调整private void shiftDown(int index/*要进行调整的节点的下标*/) {int child = index * 2 + 1;//左孩子下标if(child > size - 1) return;while(child <= size - 1) {if(child + 2 <= size && array[child] < array[child + 1]) child += 1;if(array[child] > array[index]) {swap(index, child);index = child;child = index * 2 + 1;}else break;}}//向上调整private void shiftup(int index) {int parent = (index - 1) / 2;while(parent >= 0) {if(array[parent] < array[index]) {swap(parent , index);index = parent;if(index - 1 < 0) break;//防止死循环parent = (index - 1) / 2;}else break;}}private  void swap(int left , int right) {int cur = array[left];array[left] = array[right];array[right] = cur;}//扩容，暂定1.5倍扩容private void expansion() {int[] newArray = new int[(int) (1.5 * array.length)];for(int i = 0;i < array.length;i ++) {newArray[i] = array[i];}array = newArray;}

队列+宽搜

队列 + 宽搜问题框架：

       List<List<Node>> lists = new LinkedList<>();Queue<Node> queue = new LinkedList<>();queue.add(root);while(! queue.isEmpty()) {int size = queue.size();List<Node> list = new LinkedList<>();for(int i = 0;i < size;i ++) {Node cur = queue.poll();list.add(cur);List<Node> nodes = cur.children;for(int j = 0;j < nodes.size();j ++) {queue.add(nodes.get(j));}}lists.add(list);}
//如果题目没有要求返回List<List<>>格式的数据，那么循环里size和第一个for循环的逻辑就可以去掉了

最基础 ：层序遍历：. - 力扣（LeetCode）

 二叉树每层最大值：加一个比较逻辑即可

. - 力扣（LeetCode）

锯齿形输出二叉树：

. - 力扣（LeetCode）

二叉树最大宽度：. - 力扣（LeetCode）

俩个解法：

1：还是套用层序遍历的模板，但是碰见子节点是null要将null存储进队列，

如何统计最大宽度？设置一个局部变量，在将子节点入队列时，每入一个子节点给变量加一，但是只有当子节点碰到数字时才将局部变量的值给全局统计变量，这样就能避免树的最后一个节点是null导致统计数量比实际高的问题

问题：如果题目中给出一个层数很高的树，比如单链表1500层，这个时候如果要去加null的话那么这个解法就会超时和超空间。

2：

前置知识：如果规定根节点编号为0，那么对于这整个二叉树来说：左子树编号： 2 * 根节点编号 + 1   右子树编号：2 * 根节点编号 + 2

解法：多给节点维护一个编号信息，这样我们就不用往队列加null节点了，直接正常入队列然后通过下标计算最大宽度即可：

    public int widthOfBinaryTree(TreeNode root) {if(root == null) return 0;List<Pair<TreeNode , Integer>> list = new LinkedList<>();list.add(new Pair<>(root , 0));int width = 1; //宽度while(list.size() != 0) {List<Pair<TreeNode , Integer>> newList = new LinkedList<>(); for(int i = 0;i < list.size();i ++) {//将下一层节点如队列Pair<TreeNode , Integer> pair = list.get(i);TreeNode cur = pair.getKey();if(cur.left != null) newList.add(new Pair<>(cur.left , 2 * pair.getValue() + 1));if(cur.right != null) newList.add(new Pair<>(cur.right , 2 * pair.getValue() + 2));}if(newList.size() != 0)//通过下标计算宽度width = Math.max(width , newList.get(newList.size() - 1).getValue() - newList.get(0).getValue() + 1);list = newList;//直接进行覆盖，相当于将上一层元素出队列}return width;}