Skip to main content

Queue

622. Design Circular Queue​

tip

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer". One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values. Implement the MyCircularQueue class:

  • MyCircularQueue(k) Initializes the object with the size of the queue to be k.
  • int Front() Gets the front item from the queue. If the queue is empty, return -1.
  • int Rear() Gets the last item from the queue. If the queue is empty, return -1.
  • boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
  • boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
  • boolean isEmpty() Checks whether the circular queue is empty or not.
  • boolean isFull() Checks whether the circular queue is full or not. You must solve the problem without using the built-in queue data structure in your programming language. 
class MyCircularQueue {
    private int[] arr;
    private int capacity;
    private int head = 0;
    private int tail = 0;

    public MyCircularQueue(int k) {
        arr = new int[k];
        capacity = k;
    }
    
    public boolean enQueue(int value) {
        if(isFull()) return false;
        arr[tail % capacity] = value; // 因为是一个环，所以要取余数
        tail ++; // 队尾指针后移，队尾指针指向的是队尾元素的后一个元素
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()) return false;
        head ++; // 出队，直接头指针后移
        return true;
    }
    
    public int Front() {
        if(isEmpty()) return -1;
        return arr[head % capacity];
    }
    
    public int Rear() {
        if(isEmpty()) return -1;
        // 队尾指针指向的是队尾的后一个元素
        return arr[(tail - 1) % capacity];
    }
    
    public boolean isEmpty() {
        // 当头尾相等正向同一个，说明队列为空
        return head == tail;
    }

    public boolean isFull() {
        // 尾结点位置-头结点位置 长度 等于 容量
        // 注意tail队尾指针是指向队尾元素后一个位置的
        // 如果有4个元素：[1,2,3,4, null]；位置：5 - 1 = 4；正好等于队列容量
        return tail - head == capacity; 
    }
}

933. Number of Recent Calls

tip

You have a RecentCounter class which counts the number of recent requests within a certain time frame. Implement the RecentCounter class:

  • RecentCounter() Initializes the counter with zero recent requests.
  • int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t]. It is guaranteed that every call to ping uses a strictly larger value of t than the previous call. 
Example 1:
Input ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]]
Output [null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], range is [2,3002], return 3
class RecentCounter {
    Queue<Integer> queue;

    public RecentCounter() {
        queue = new LinkedList<>();
    }

    public int ping(int t) {
        // 理解题目意思：加入值后，有效区间是[t-3000, t]；
        // 所以需要淘汰的小于t-3000的所有值，所以循环比较后出栈
        // 记住java里面的入队列是offer；而不是enqueue
        queue.offer(t);
        int min = t - 3000;
        // 这里千万记得，循环出栈
        // 记住java里面的出队列是poll()；而不是dequeue
        while(queue.peek() < min) queue.poll();
        return queue.size(); // 返回size
    }
}

1670. Design Front Middle Back Queue​

tip

Design a queue that supports push and pop operations in the front, middle, and back. Implement the FrontMiddleBack class:

  • FrontMiddleBack() Initializes the queue.
  • void pushFront(int val) Adds val to the front of the queue.
  • void pushMiddle(int val) Adds val to the middle of the queue.
  • void pushBack(int val) Adds val to the back of the queue.
  • int popFront() Removes the front element of the queue and returns it. If the queue is empty, return -1.
  • int popMiddle() Removes the middle element of the queue and returns it. If the queue is empty, return -1.
  • int popBack() Removes the back element of the queue and returns it. If the queue is empty, return -1. Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example:
  • Pushing 6 into the middle of [1, 2, 3, 4, 5] results in [1, 2, 6, 3, 4, 5].
  • Popping the middle from [1, 2, 3, 4, 5, 6] returns 3 and results in [1, 2, 4, 5, 6].
arrayList版本
class FrontMiddleBackQueue {
    List<Integer> list; // list实现，但是复杂度过高，因为要移动元素
    public FrontMiddleBackQueue() {
        list = new ArrayList<>();
    }
    
    public void pushFront(int val) {
        list.add(0, val);// 在list头部插入
    }

    /**
     * 如果是奇数[1,2,3] 插入位置2；下标1
     * 如果是偶数[1,2,3,4] 插入位置3；下标2
     * => 一个列表获取中间位置靠后，下标从0开始的话，直接除2
     */
    public void pushMiddle(int val) {
        // 如果是[1,2]中间位置是 2 - 1 = 1 / 2 = 0，显然不对
        // 如果是[1,2,3,4,5]中间位置是3，下标是2；（5 - 1）= 4 / 2 = 2;
        // 如果是[1,2,3,4,5,6]中间位置是3，下标是2：(6 - 1) = 5 / 2 = 2;
        // 所以中间位置是：list.size() / 2; 
        int pos = list.size() / 2;
        list.add(pos, val);
    }
    
    public void pushBack(int val) {
        list.add(val);
    }
    
    public int popFront() {
        if(list.isEmpty()) return -1;
        return list.remove(0);
    }
    
    /**
     * 如果是奇数[1,2,3] 删除位置2；下标1
     * 如果是偶数[1,2,3,4] 删除位置2；下标1
     * => 一个列表获取中间节点靠左，下标从0开始的话，直接(len - 1) / 2
     */
    public int popMiddle() {
        if(list.isEmpty()) return -1;
        int pos = (list.size() - 1) / 2;
        return list.remove(pos);
    }
    
    public int popBack() {
        if(list.isEmpty()) return -1;
        return list.remove(list.size() - 1);
    }
}
双向链表版本
class FrontMiddleBackQueue {
   class Node {
        public int val;
        public Node next;
        public Node prev;
        public Node() {}

        public Node(int val) {
            this.val = val;
        }
    }

    private int size;
    private Node head;
    private Node tail;
    private Node mid;

    public FrontMiddleBackQueue() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
        mid = head;
        size = 0;
    }

    public void pushFront(int val) {
        // 中间节点什么时候移动？插入值之后
        addNodeBefore(head.next, val);
        if(size == 1) mid = mid.next; // []
        // [2,3] => [1,2,3] 不移动；[2,3,4] => [1,2,3,4] 前移
        else if(size % 2 == 0) mid = mid.prev;
    }

    public void pushMiddle(int val) {
        if(size == 0) { // []
            addNodeBefore(tail, val);
            mid = mid.next;
        } else if(size % 2 == 1) { // [1,2,3]
            addNodeBefore(mid, val);
            mid = mid.prev;
        }else { // [1,2,3,4]
            addNodeBefore(mid.next,val);
            mid = mid.next;
        }
    }

    public void pushBack(int val) {
        // 中间节点什么时候移动？
        addNodeBefore(tail, val);
        if(size == 1) mid = head.next;
        // [1,2] => [1,2,3] 后移; [1,2,3] => [1,2,3,4] 不移
        else if(size % 2 == 1) mid = mid.next;
    }

    public int popFront() {
        if(size == 0) return -1;
        if(size == 1) mid = head;
        // [1,2,3] => [2,3] 不需要移动 || [1,2,3,4] => [2,3,4] 后移
        if(size % 2 == 0) mid = mid.next;
        return removeNode(head.next);
    }

    public int popMiddle() {
        if(size == 0) return -1;
        // [1,2,3] 移除2 [1,3]  向前移动 || [1,2,3,4] 移除3 [1,2,4] 向后移动
        Node temp = size % 2 == 1 ? mid.prev : mid.next;
        int result = removeNode(mid);
        mid = temp;
        return result;
    }

    public int popBack() {
        if(size == 0) return -1;
        // [1,2,3] => [1,2] 向前移动 || [1,2,3,4] => [1,2,3] 不需要移动
        if(size % 2 == 1) mid = mid.prev;
        return removeNode(tail.prev);
    }

    private int removeNode(Node node) {
        if(size == 0) return -1;
        Node temp = node.next;
        node.prev.next = temp;
        temp.prev = node.prev;
        node.next = null;
        node.prev = null;
        size --;
        return node.val;
    }

    /**
     * 在node节点前插入新的node
     */
    private void addNodeBefore(Node node, int val) {
        Node newNode = new Node(val);
        // 保存插入node节点的前一个节点
        Node prevNode = node.prev;
        // 将新的节点与当前节点建立关系
        newNode.next = node;
        node.prev = newNode;
        // 将新的节点与之前节点建立关系
        prevNode.next = newNode;
        newNode.prev =  prevNode;
        size ++;
    }
}

239. Sliding Window Maximum​

tip

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
class Solution {
   public int[] maxSlidingWindow(int[] nums, int k) {
       Deque<Integer> deque = new LinkedList<>();
       // 这里为什么是len - k + 1;
       // 因为如果是；[1,2,3,4],k = 2;只有[1,2],[2,3],[3,4]
       // 共3窗口 len - k + 1 = 4 - 2 = 1 = 3
       int[] result = new int[nums.length - k + 1];
       for(int right = 0; right < nums.length; right++) {
           // 如果队列不为空，并且要加入的元素比队尾元素大，队尾出栈，
           // 这里就是为了保持队列中元素单调递减
           // 这里容易写错，是比较值，不是下标
           while(!deque.isEmpty() && nums[right] > nums[deque.peekLast()]) {
               deque.pollLast();
           }
           // 加入元素
           deque.offer(right);
           // 计算窗口左边界
           int left = right - k + 1;
           // 如果队列中最大元素下标超过了窗口左边界，队列头(最大元素下标)出栈
           if(left > deque.peek()) deque.poll();
           // 队列头出栈，最大值放入result中，
           // 但是这里需要跳过第一个窗口没有形成的情况
           if(left >= 0) result[left] = nums[deque.peek()];
       }
       return result;
   }
}

99999. Min Heap & Max Heap​

// 默认小顶堆
PriorityQueue<Integer> minHeapPq = new PriorityQueue<>();

// 定义排序顺序，大顶堆
PriorityQueue<Integer> maxHeapPq = new PriorityQueue<>(Comparator.reverseOrder());

703. Kth Largest Element in a Stream​

tip

Design a class to find the k(th) largest element in a stream. Note that it is the k(th) largest element in the sorted order, not the k(th) distinct element. Implement KthLargest class:

  • KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
  • int add(int val) Appends the integer val to the stream and returns the element representing the k(th) largest element in the stream.
Example 1:
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8
class KthLargest {
    private int k;
    // 为什么要使用minHeap?
    // 题目求得是第K个【最大】的元素，不是第K个大的元素
    // 也就是5,4,3,2,1;第3个最大的，也就是3;只能取堆顶，那顺序必须是 3,4,5
    // 所以这里使用minHeap;堆顶就是倒数第K大的元素；
    private PriorityQueue<Integer> pq = new PriorityQueue<>();

    public KthLargest(int k, int[] nums) {
        for(int num : nums) pq.offer(num);// 这里初始化丢到堆里
        this.k = k;
    }
    
    public int add(int val) {
        pq.offer(val); // add
        // 这里要循环判断，让堆的大小等于K的大小，这样取堆顶元素才是第K个数
        while(pq.size() > k) pq.poll();
        return pq.peek(); // 直接取堆顶
    }
}

17.14. Smallest K LCCI​

tip

Design an algorithm to find the smallest K numbers in an array.

Example:
Input:  arr = [1,3,5,7,2,4,6,8], k = 4
Output:  [1,2,3,4]
solution 1
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        // 最小的K个数，要保存，1...K，使用max heap; 
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for(int val : arr) {
            pq.offer(val);
            // 每次加入，如果大小超过k，丢弃掉最大的
            if(pq.size() > k) pq.poll();
        }
        int[] result = new int[k];
        for(int i = 0; i < k; i++)  result[i] = pq.poll();
        return result;
    }
}
solution 2
class Solution {
    // 使用maxHeap全部加入，直接取top k
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int num : arr) pq.offer(num);
        int[] result = new int[k];
        for(int i = 0; i < result.length; i++) {
            result[i] = pq.poll();
        }
        return result;
    }
}

23. Merge k Sorted Lists​

tip

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. 

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are: [ 1->4->5,  1->3->4,  2->6 ]
merging them into one sorted list: 1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 构建MinHeap.
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)-> a.val - b.val);
        // 这里原本是将所有的节点放入，但是题目是lists里面的每个链表是排序好的
        // 如果全部放入堆，那堆每次插入的复杂度是O(logN)，所以没必要
        // 只需要保持堆的大小为lists.size();每次比较每条链表的头部元素即可
        for(ListNode node : lists) {
            // 这里有坑，测试用例里，有空节点
            if(node != null) pq.offer(node);
        }
        ListNode head = new ListNode();
        ListNode tail = head;

        while(!pq.isEmpty()) {
            ListNode minNode = pq.poll();
            tail.next = minNode;
            tail = tail.next; // 始终指向队尾
            if(minNode.next != null) pq.offer(minNode.next);
        }
        return head.next;
    }
}