Queue

先進先出的容器，有以下幾個常見的操作：

push 尾端加入元素
pop 頂端刪除元素
front 回傳頂端元素
back 回傳尾端元素
empty 確認是否為空
size 回傳元素個數

Priority Queue

1	template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

容器內部的元素依照一定順序排列，每次取出位於排列頂端的元素，預設為遞減排序 (由頂部至尾部遞減)，如果要改為遞增可以加上 greater<T>，或是使用自己寫的 cmp 排序，其餘操作與普通的 Queue 相同。

練習

LeetCode 703. Kth Largest Element in a Stream

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]

Solution:

class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> pq;
    int len;
    KthLargest(int k, vector<int>& nums) {
        len = k;
        for(int i = 0; i < nums.size(); i++){
            pq.push(nums[i]);
            if(pq.size() > len) pq.pop();
        }
    }
    
    int add(int val) {
        pq.push(val);
        if(pq.size() > len) pq.pop();
        return pq.top();
    }
};

建立一個遞增的 Priority Queue，並且限制其長度為 k，當長度大於 k 的時候就把頂端較小的元素刪除，這樣就可以保持尾端剛好是第 k 大的元素。

LeetCode 239. Sliding Window Maximum

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]

Solution:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int, int>> pq;
        vector<int> ans;
        for(int i = 0; i < k; i++){
            pq.push({nums[i], i});
        }
        ans.push_back(pq.top().first);
        for(int i = k; i < nums.size(); i++){
            pq.push({nums[i], i});
            while((pq.top()).second < i - k + 1 || (pq.top()).second > i) pq.pop();
            ans.push_back(pq.top().first);
        }
        return ans;
    }
};

建立一個 Priority Queue 裡面儲存的是一個 pair，pair 內的數字分別表示元素的數值以及所在位置，每次 sliding window 移動時，加入新元素，之後判斷位於頂端的元素位置是否在區間內部，否則將其去除，這樣就可以找到區間內的最大值。

LeetCode 295. Find Median from Data Stream

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.

Example 1:
Input
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Solution:

class MedianFinder {
public:
    priority_queue<double, vector<double>, greater<double>> pq1;
    priority_queue<double> pq2;
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if(pq2.empty()){
            pq2.push(num);
            return;
        }
        double m;
        if((pq1.size() + pq2.size()) % 2 == 0) m = (pq1.top() + pq2.top()) / 2;
        else m = pq2.top();
        if(num > m){
            pq1.push(num);
            if(pq1.size() == pq2.size() + 1){
                pq2.push(pq1.top());
                pq1.pop();
            }
        }else{
            pq2.push(num);
            if(pq1.size() + 2 == pq2.size()){
                pq1.push(pq2.top());
                pq2.pop();
            }
        }
    }
    
    double findMedian() {
        if((pq1.size() + pq2.size()) % 2 == 0) return (pq1.top() + pq2.top()) / 2;
        return pq2.top();
    }
};