栈 队列 堆

栈：先进后出的线性表
队列：先进先出的线性表

Leecode 225: 队列实现栈：采用Deque(或者使用LinkedList)：含有的方法

实现：

/**
采用双端队列：Deque实现，
*/
class MyStack {
    private Deque<Integer> list;
    /** Initialize your data structure here. */
    public MyStack() {
    list = new LinkedList<Integer>();
    }
    /** Push element x onto stack. */
    public void push(int x) {
    list.add(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
    return list.pollLast();
    }
    /** Get the top element. */
    public int top() {
     return list.peekLast();
    }
    /** Returns whether the stack is empty. */
    public boolean empty() {
    return list.size()==0;
    }
}
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Leetcode 232:栈实现队列：

实现：利用栈实现队列必须使用两个栈，使用两个栈可以把原来栈先进后出变成先进先出

class MyQueue {
    private Stack<Integer> stack1;
     private Stack<Integer> stack2;
     private Integer front;
    /** Initialize your data structure here. */
    public MyQueue() {
     stack1 = new Stack<>();
     stack2 = new Stack<>();
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
    if(stack1.isEmpty()){
        front =x;
    }
     while(!stack1.isEmpty()){
        stack2.push(stack1.pop()); 
     }
     stack2.push(x);
     while(!stack2.isEmpty()){
         stack1.push(stack2.pop());
     }
    }
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
     return stack1.pop();
    }
    /** Get the front element. */
    public int peek() {
     if(!stack1.isEmpty())front =stack1.peek();
     return front;
    }
    /** Returns whether the queue is empty. */
    public boolean empty() {
     return stack1.isEmpty();
    }
}
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

Leetcode 155:最小栈

// class MinStack {
//     private Stack <Integer> dataStack ;//数据栈
//     private Stack <Integer> minStack;//最小值栈
//     //private int min=0;//用于记录最小值；
//    // private int subMin =0; //用于记录上一个最小值
//     /** initialize your data structure here. */
//     public MinStack() {
//      dataStack =new Stack<Integer>();
//      minStack = new Stack<Integer>();
//     }
//     public void push(int x) {
//      dataStack.push(x);
//      if(minStack.isEmpty()){
//          minStack.push(x);
//      }else{
//          if(x<minStack.peek()){
//          minStack.push(x);
//          }else{
//               minStack.push(minStack.peek());
//          }
//      }
//     }
//     //同时弹出
//     public void pop() {
//       dataStack.pop();
//       minStack.pop();
//     }
//     public int top() {
//      return dataStack.peek();
//     }
//     public int getMin() {
//      return minStack.peek();
//     }
// }
//优化后结果
// class MinStack {
//     private Stack <Integer> dataStack ;//数据栈
//     private Stack <Integer> minStack;//最小值栈
//     //private int min=0;//用于记录最小值；
//    // private int subMin =0; //用于记录上一个最小值
//     /** initialize your data structure here. */
//     public MinStack() {
//      dataStack =new Stack<Integer>();
//      minStack = new Stack<Integer>();
//     }
//     public void push(int x) {
//      dataStack.push(x);
//      if(minStack.isEmpty()||x<=minStack.peek()){
//          minStack.push(x);
//      }
//     }
//     public void pop() {
//       if(dataStack.pop().equals(minStack.peek()))
//        minStack.pop();
//     }
//     public int top() {
//      return dataStack.peek();
//     }
//     public int getMin() {
//      return minStack.peek();
//     }
// }
//采用Node实现
class MinStack {
    private Stack<Node> stack;
    //private int min=0;//用于记录最小值；
   // private int subMin =0; //用于记录上一个最小值
    /** initialize your data structure here. */
    public MinStack() {
     stack =new Stack<>();
    }
    public void push(int x) {
     if(stack.isEmpty())
      stack.push(new Node(x,x));
     else
      stack.push(new Node(x,Math.min(stack.peek().min,x)));
    }
    public void pop() {
      stack.pop();
    }
    public int top() {
      return stack.peek().val;
    }
    public int getMin() {
      return stack.peek().min;
    }
    class Node{
        int min;
        int val;
        public Node(int val,int min){
            this.val =val;
            this.min =min;
        }
    }
}
/**
 * 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.getMin();
 */
//一个栈完成，当即将压入的值小于记录的min最小值，先把当前最小值压入，然后再压入当前值，当弹出的最小值等于最小
小值时，先弹出，然后把最小值赋值为下一个即将弹出的值（第二小）；
class MinStack {
    private Stack<Integer> stack;
    private int min = Integer.MAX_VALUE;//记录当前最小值
    public MinStack() {
     stack =new Stack<>();
    }
    public void push(int x) {
     if(x<=min){
         stack.push(min);//如果压入的值比当前最小值还小，先把当前最小压入栈，然后再压入该值
         min =x;//最小值改变
     }
     stack.push(x);//压入当前值
    }
    public void pop() {
      if(stack.pop()==min){
          min =stack.pop();
      }
    }
    public int top() {
      return stack.peek();
    }
    public int getMin() {
      return min;
    }
}

Leetcode 946:验证栈序列：
思路：借助辅助栈：将pushed数组压入栈，如果栈顶数组等于poped数组中poped[index],index是验证两者通过的个数，则将栈顶数组推出

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
     Stack<Integer> stack = new Stack<Integer>();
     int j =0;//两个数组记录符合入栈出栈的数目
     for(int x: pushed){
         stack.push(x);
         while(!stack.isEmpty()&&j<pushed.length&&stack.peek()==popped[j]){
             stack.pop();
             j++;
         }
     }
     return j==pushed.length;//全部符合为True
    }
}

Leetcode:215:数组中第k大的：
优先队列的思路是很朴素的。因为第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小堆：

1、如果当前堆不满，直接添加；

2、堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新都到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。

说明：这里最合适的操作其实是 replace，即直接把新读进来的元素放在堆顶，然后执行下沉（siftDown）操作。Java 当中的 PriorityQueue 没有提供这个操作，只好先 poll() 再 offer()。

优先队列的写法就很多了，这里例举一下我能想到的（以下的写法大同小异，没有本质差别）。

假设数组有 len 个元素。

思路1：把 len 个元素都放入一个最小堆中，然后再 pop() 出 len - k 个元素，此时最小堆只剩下 k 个元素，堆顶元素就是数组中的第 k 个最大元素。

思路2：把 len 个元素都放入一个最大堆中，然后再 pop() 出 k - 1 个元素，因为前 k - 1 大的元素都被弹出了，此时最大堆的堆顶元素就是数组中的第 k 个最大元素。

import java.util.PriorityQueue;

public class Solution {

    // 根据 k 的不同，选最大堆和最小堆，目的是让堆中的元素更小
    // 思路 1：k 要是更靠近 0 的话，此时 k 是一个较大的数，用最大堆
    // 例如在一个有 6 个元素的数组里找第 5 大的元素
    // 思路 2：k 要是更靠近 len 的话，用最小堆

    // 所以分界点就是 k = len - k

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if (k <= len - k) {
            // System.out.println("使用最小堆");
            // 特例：k = 1，用容量为 k 的最小堆
            // 使用一个含有 k 个元素的最小堆
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
            for (int i = 0; i < k; i++) {
                minHeap.add(nums[i]);
            }
            for (int i = k; i < len; i++) {
                // 看一眼，不拿出，因为有可能没有必要替换
                Integer topEle = minHeap.peek();
                // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
                if (nums[i] > topEle) {
                    minHeap.poll();
                    minHeap.add(nums[i]);
                }
            }
            return minHeap.peek();

        } else {
            // System.out.println("使用最大堆");
            assert k > len - k;
            // 特例：k = 100，用容量为 len - k + 1 的最大堆
            int capacity = len - k + 1;
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(capacity, (a, b) -> b - a);
            for (int i = 0; i < capacity; i++) {
                maxHeap.add(nums[i]);
            }
            for (int i = capacity; i < len; i++) {
                // 看一眼，不拿出，因为有可能没有必要替换
                Integer topEle = maxHeap.peek();
                // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
                if (nums[i] < topEle) {
                    maxHeap.poll();
                    maxHeap.add(nums[i]);
                }
            }
            return maxHeap.peek();
        }
    }
}

采用快排：

// class Solution {
//     public int findKthLargest(int[] nums, int k) {
//   //优化：当k较小的时候使用最小堆，k较大的时候较大的时候采用最大堆
//   int len = nums.length;
//    if(k<=len-k){//采用最小堆,lamda表达式实现Comparable接口：默认最小堆
//     PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k,(a,b)->a-b);
//     for(int num:nums){
//         if(pq.size()<k){
//             pq.add(num);
//         }else{
//             if(num>pq.peek()){
//             pq.poll();
//             pq.add(num);
//             }
//         }
//     }
//     return pq.peek();
//     }else{
//         int capacity = len-k+1;
//         PriorityQueue<Integer>pq_max =new PriorityQueue<>(capacity,(a,b)->b-a);
//         for(int num:nums){
//             if(pq_max.size()<capacity){
//                 pq_max.add(num);
//             }else{
//                 if(num<pq_max.peek()){
//                     pq_max.poll();
//                     pq_max.add(num);
//                 }
//             }
//         }
//         return pq_max.peek();
//     }

//     }
// }
public class Solution {

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;

        // 转换一下，第 k 大元素的索引是 len - k
        int target = len - k;
      //  if(len==1) return nums[len-1];

      //如果是快速排序则需要index前后都需要排
        while (true) {
            int index = partition(nums, left, right);
            if (index == target) {
                return nums[index];
                //index小于目标，直接从index右边进行切分
            } else if (index < target) {
                left = index + 1;
            } else {
                //大于目标，从index左边进行切分
                right = index - 1;
            }
        }
    }

    /**
     * 在数组 nums 的子区间 [left, right] 执行 partition 操作，返回 nums[left] 排序以后应该在的位置
     * 在遍历过程中保持循环不变量的语义
     * 1、[left + 1, j] < nums[left]
     * 2、(j, i] >= nums[left]
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
     public int partition(int[] nums, int left, int right) {
    //     int pivot = nums[left];
    //     int j =left;
    //     for (int i = left + 1; i <= right; i++) {
    //         if (nums[i] < pivot) {
    //             // 小于 pivot 的元素都被交换到前面
    //             j++;
    //             swap(nums, j, i);
    //         }
    //     }
    //     // 在之前遍历的过程中，满足 [left + 1, j] < pivot，并且 (j, i] >= pivot
    //     swap(nums, j, left);
    //     // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
    //     return j;
        /**************快速排序完整版************/
    //      int i = left;
    //    int j = right;
    //    int vo = nums[left];
    //    while (i < j) {
    //        //从右边开始
    //        while (vo <=nums[j]&&i<j) {
    //            j--;
    //        }
    //        //从左边开始
    //        while (vo >= nums[i]&&i<j) {
    //            i++;
    //        }
    //        //如果找到了
    //        if (i < j) {
    //            swap(nums, i, j);

    //        }
    //    }
    //    //调整首位置元素到准确位置
    //    swap(nums,left,j);
    //    //返回准备位置作为切分位置
    //    return j;
    /**完整快速排序方法**/
     int i =left;
        int j =right+1;
        int vo =nums[left];
        while(true){
            while(i<right&&nums[++i]<vo);
            while(j>left&&vo<nums[--j]);
            if(i>=j)break;
            swap(nums,i,j);
        }
        swap(nums,left,j);
        return j;

    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

Leetcode:295 数据流的中位数 采用大顶锥和小顶锥结合方式

class MedianFinder {
    //采用大小堆组合
    /** initialize your data structure here. */
    PriorityQueue<Integer> maxPQ ;
    PriorityQueue<Integer> minPQ;
    //初始化
    public MedianFinder() {
     maxPQ = new PriorityQueue<>((a,b)->b-a);
     minPQ = new PriorityQueue<>();
    }
    //保证大顶锥比小顶锥多1
    public void addNum(int num) {
     maxPQ.offer(num);
     minPQ.offer(maxPQ.poll());
     if(maxPQ.size()<minPQ.size()){
         maxPQ.offer(minPQ.poll());
     }
    }

    public double findMedian() {
    if(minPQ.size()<maxPQ.size()){
        return maxPQ.peek();
    }
    else{
        return (double) (maxPQ.peek()+minPQ.peek())/2;
    }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */