剑指OFFER思路总结与代码分享——栈和堆篇(Java实现)

注：顺序是先筛选分类再按LeeCode上的通过率排的，每题最后的总结代码都是在LeeCode上跑过的，应该没啥问题。但是思路中的代码都是直接在CSDN编辑器里徒手敲的，若有笔误还烦请告知，蟹蟹~

09 用两个栈实现队列

首先LinkedList有栈的功能，Stack继承自Vector，底层是用数组实现的，需要各种copyOf去扩容，会导致速度变慢，我们就用LinkedList的push()与pop()来模拟栈即可。
它给我们两个栈，要求完成一个队列的操作，入队没啥好说的，进栈就完事了；出队就是把第一个栈内的东西统统倒到第二个栈里，就又变正了，然后我们出第二个栈最上面的那个即可，有种“正=>反=>反=>正”的感觉。

class CQueue {

    LinkedList<Integer> stack1,stack2;
    
    public CQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(stack2.isEmpty()){
            if(stack1.isEmpty()){	
            	//两个栈都空，队列就是空的
                return -1;
            }
            while(!stack1.isEmpty()){		
            	//把栈1的东西全弹进栈2里，由stack1的反变成stack2的正
                stack2.push(stack1.pop());
            }   
        }
        //弹栈2最顶上那个
        return stack2.pop();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

30 包含min函数的栈

不太会算时间复杂度啊，看了一下速度战胜了97%应该满足要求了吧，卑微。
读完题第一反应：

这啥玩意…脑补了一下过程，写了个int min = 0;，然后发现不对，终于知道这题要考啥了，因为它要O(1)嘛，意思就是在不让你遍历的情况下直接告诉它你这个栈的最小值是啥，万一你min记录的那个值被弹出去了，然后它问你：现在最小值是啥啊？你就傻了，所以咱们要以空间换时间，怎么个换法就是这题的考点了。
我们另外再开一个栈，专门记录最小值，新的值进来我们要问自己，这个值是不是比我们以前记录的值小？要是小的话把它压入栈（相等的话也要压入栈哦~写个[3,2,1,1]想想，相等不压进去等1弹出记录的栈顶就是2了，但是其实最小值还是1），重复这么做，等弹出的时候问自己，这个值是我记录的栈顶的值么？如果是的话把它和要弹出的值一起弹出去，这样我的栈顶就是原来第二小的值了。花里胡哨的总结就是再另外维护一个递减的栈就完事了。
另外要在这提一个知识点，我一开始想当然的用linkedlist.getLast();去拿栈顶的元素，结果发现拿的是栈底的，查了一下发现：

LinkedList add 是加在list尾部.
LinkedList push 施加在list头部. 等同于addFirst.

切记切记，容易搞混。简单说来，你要用栈的那套你就一直用，包括push/pop/peek，用队列那套就用add/poll，这样不容易出错。

class MinStack {

   LinkedList<Integer> list1,list2;
   /** initialize your data structure here. */
   public MinStack() {
       list1 = new LinkedList<>();
       list2 = new LinkedList<>();
   }
   
   public void push(int x) {
       list1.push(x);
       //list2空就直接加，不空则看看栈顶的值是否比咱们的大或者相等
       //要是比咱们小的话就说明咱们不会影响到最小值的变更，就拉倒了
       if(list2.isEmpty() || list2.peek() >= x){
           list2.push(x);
       }
       
   }
   
   public void pop() {
   	   //相等则一起弹出
       if(list1.peek().equals(list2.peek())){
           list1.pop();
           list2.pop();
       }else{
       	   //不相等则自己弹出
           list1.pop();
       }
   }
   
   public int top() {
       return list1.peek();
   }
   
   public int min() {
       return list2.peek();
   }
}

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/

待续待续

转载：https://blog.csdn.net/qq_36329973/article/details/105459735