与栈/队列相关的算法题

1、使用暴力方法解决，两层循环，时间复杂度O(N*M)

2、使用单调队列来解决：

单调队列是一个从大到小的队列，队列内存放的是可能是窗口内的最大元素。单调栈的细节如图：

单调队列的操作：

（1）push(x) ：x需要与队列入口的值进行比较，如果x小于等于队列入口值，则直接插入，如果x大，则队列尾部弹出，重新比较，直到队列中没有元素，或者x小于等于队列入口值。

（2）pop() ：如果窗口弹出的值和队列出口处的值一致，则弹出队列出口值，否则不变。

class MyQueue{
public:
    deque queue;
    void push(int x){
        while(!queue.empty() && x > queue.back()){
            queue.pop_back();
        }
        queue.push_back(x);
    }
    void pop(int x){
        if(!queue.empty() && x == queue.front()){
            queue.pop_front();
        }
    }
    int front(){
        return queue.front();   
    }
};
class Solution { 
public:
    vector maxSlidingWindow(vector& nums, int k) {
        vector result;
        MyQueue que;
        for(int i = 0; i < k; i++){
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for(int i = k, j = 0; i < nums.size(); i++, j++){
            que.pop(nums[j]);
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }
};

思路一：

1、需要对元素出现的频率进行统计，使用map进行统计

2、对出现的频率进行排序，使用小顶堆（和优先级队列的效果一样，套了个队列的壳子，其实就是堆）存放，每次将小的k个元素排除，剩下的k个就是最大的。

3、找出频率最大的k个元素。

class Solution {
public:
    class CompareFunction{ //因为不是基本数据类型，所以需要自定义比较类
        public:
            //比较类中实现operator函数
            bool operator()(const pair& le, const pair& ri){
                return le.second > ri.second; //注意，左边大于右边时建立小顶堆
            }
    };
    vector topKFrequent(vector& nums, int k) {
        unordered_map map;
        priority_queue, vector>, CompareFunction> result;
        for(int i =0; i < nums.size(); i++){
            if(map.find(nums[i]) != map.end()){
                map[nums[i]]++;
            }
            else{
                map[nums[i]] = 1;
            }
        } 
        for(unordered_map::iterator it = map.begin(); it != map.end(); it++){
            result.push(*it);
            if(result.size() > k){
                result.pop();
            }
        }
        vector res(k);
        for(int i = k-1; i>=0; i--){
            res[i] = result.top().first;
            result.pop();
        }
        //vector res(result.begin(), result.end());
        return res;
    }
};