# 基础

队列的底层可由数组或链表实现。

type Queue []interface {}

func (queue Queue) Len() int {
    return len(queue)
}

func (queue Queue) IsEmpty() bool  {
    return len(queue) == 0
}

func (queue Queue) Cap() int {
    return cap(queue)
}

func (queue *Queue) Push(value interface{})  {
    *queue = append(*queue, value)
}

func (queue Queue) Top() interface{}  {
    if len(queue) == 0 {
        return nil
    }
    return queue[0]
}

func (queue *Queue) Pop() interface{}  {
    refQueue := *queue
    if len(refQueue) == 0 {
        return nil
    }
    value := refQueue[0]
    *queue = refQueue[1:]
    return value
}

# 实践

# 单调队列求滑动窗口最大值

滑动窗口最大值

单调队列。单调队列的性质是维持有序序列，最值位于最头部，常用于不断有值替换（去除最久的，加入最新的）的场景中取最值。

type MonoQueue []int

func (m *MonoQueue)Push(val int) {
    mref := *m
    for len(mref) > 0 && val > mref[len(mref) - 1] {
        mref = mref[:len(mref) - 1]
    }
    *m = append(mref, val)
}

func (m *MonoQueue)Pop(val int) {
    mref := *m
    if len(mref) > 0 && val == mref[0] {
        mref = mref[1:]
    }
    *m = mref
}

func (m *MonoQueue)Front() int {
    return (*m)[0]
}

func maxSlidingWindow(nums []int, k int) []int {
    ret := []int{}
    m := MonoQueue{}
    for i := 0; i < k; i++ {
        m.Push(nums[i])
    }
    ret = append(ret, m.Front())
    for i := k; i < len(nums); i++ {
        m.Pop(nums[i - k])
        m.Push(nums[i])
        ret = append(ret, m.Front())
    }
    return ret
}

# 最小k个数

暴力：排序
优先队列，最大堆

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if (k==0 || k > input.size()) return ret;
        priority_queue<int> pq;
        for (const int val : input) {
            if (pq.size() < k) {
                pq.push(val);
            } else if (val < pq.top()) {
                pq.pop();
                pq.push(val);
            }
        }
 
        while (!pq.empty()) {
            ret.push_back(pq.top());
            pq.pop();
        }
        return ret;
    }
};

# 第k大数


std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        std::priority_queue<int> pq;
        for (auto i : a) {
            pq.push(i);
        }
        for (int i =0; i < K - 1; i++) {
            pq.pop();
        }
        return pq.top();
    }
};

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        return findK(a, 0, n-1, K);
    }
    
    int findK(vector<int>& a, int l, int h, int k) {
        if (l <= h) {
            int p = partition(a, l, h);
            
            if (p == k - 1) {
                return a[p];
            } else if (p < k - 1) {
                return findK(a, p + 1, h, k);
            } else {
                return findK(a, l, p - 1, k);
            }
        }
        return -1;
    }
    
    int partition(vector<int>& a, int l, int h) {
        int p = a[l];
        
        while (l < h) {
            while (l < h && a[h] <= p) {
                h--;
            }
            a[l] = a[h];
            while (l < h && a[l] >= p) {
                l++;
            }
            a[h] = a[l];
        }
        a[l] = p;
        return l;
    }
    
    void swap(vector<int>& a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
};

Previous post: 机器学习系统 3-7 - Kubeflow Next post: 算法基础 - 栈

吹拉弹唱

# 基础

# 实践

# 单调队列求滑动窗口最大值

# 最小k个数

# 第k大数