239. 滑动窗口最大值

暴力O(k * n),用单调队列（不是优先级队列，优先级序列改变了窗口内元素顺序，没法弹出），保证序列内元素时单调递减（队头始终是最大的元素）且只维护可能是最大元素的窗口元素，这样窗口移动丢弃元素同时需要队列弹出的时候，肯定是队列的头，因为其他比头小的元素早已经被弹出去了（头肯定是先进的元素，弹也是先弹旧的），不用管。具体实现三个函数。

• push，放入单调序列的时候判断，如果新加的元素比前面的元素大，则前面的元素pop_back直到队列为空或者队列元素比新加的元素大。
• pop，窗口移动移除末端元素时如果元素时队列中的头则队列头弹出pop_front，否则队列不用进行操作，该弹的元素在push里已经弹出了。
• front，返回当前时刻窗口内的最大值也就是队列的头。

C++

注意C+底层实现是deque，双向队列，从两边都可以push或者pop。

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

C#

C#中没有双向队列Deque，但可以通过双向链表LinkedList来模拟。

public class Solution {
    LinkedList<int> que = new LinkedList<int>();
    public int[] MaxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.Length - k + 1];
        for(int i = 0; i < k; i++) {
            push(nums[i]);
        }
        result[0] = front();
        for(int i = 0; i + k <nums.Length; i++) {
            pop(nums[i]);
            push(nums[i+ k]);
            result[i + 1] = (front());
        }
        return result;
    }
    void push(int val) {
        while (que.Count != 0 && val > que.Last.Value) que.RemoveLast();
        que.AddLast(val);
    }
    void pop(int val) {
        if (que.Count != 0 && val == que.First.Value) que.RemoveFirst();
    }
    int front() {
        return que.First.Value;
    }
}

347.前 K 个高频元素

用优先级队列（小顶堆），O(nlogk)只维护k个最大元素的集合，先哈希计算数字出现的频率，再遍历哈希跌代器并用小顶堆记录，每当小顶堆size>k就弹出堆头最小元素，剩余的就是k个最大的元素，按从大到小频率输出再把堆头出来的记录倒转一下。

小顶堆的定义和比较函数那有点麻烦，二刷结合完全二叉树看一下。

C++

class Solution {
    class mycomparsion {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        } 
    };
public:

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }
        priority_queue<pair<int, int>, vector<pair<int,int>>, mycomparsion> pri_que;
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if(pri_que.size() > k) {
                pri_que.pop();
            }
        }
        vector<int> result(k);
        for (int i = k - 1; i>= 0 ;i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

C#

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        Dictionary<int, int> dic = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            if(!dic.ContainsKey(nums[i]))
                dic.Add(nums[i], 1); 
            else dic[nums[i]]++;
        }
        PriorityQueue<int, int> pq = new();
        foreach(var num in dic) {
            pq.Enqueue(num.Key, num.Value);
            if(pq.Count > k) {
                pq.Dequeue();
            }
        }

        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = pq.Dequeue();
        }
        return res;
    }
}

总结

栈适合解决匹配、邻居元素消除的问题，队列适合解决数组遍历考虑窗口移动的问题（更是可以只针对维护窗口中的部分元素），

二刷

滑动窗口最大值

能想到的是，维护窗口作为一个队列，能自动排序获得最大值，但有一个问题，如果用优先级队列的话，那弹出的时候只能弹出头最大值，但窗口左端移出的并不一定就是最大值，实际上只需要维护可能是最大值的元素就可以了（push的时候一直将比放入值小的都踢出去），不需要全放，一直维护整个队列是单调的，这样弹出的时候弹队头就可以了，比队头小的压根就不在队列里。

class Solution {
public:
    deque<int> que;
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        for (int i = 0; i < k; i++) {
            push(nums[i]);
        }
        res.push_back(que.front());
        for (int i = 0; i + k < nums.size(); i++) {
            push(nums[i + k]);
            pop(nums[i]);
            res.push_back(que.front());
        }
        return res;
    }

    void push(int x) {
        while (!que.empty() && x > que.back()) {
            que.pop_back();
        }
        que.push_back(x);
    }
    void pop(int x) {
        if (x == que.front()) que.pop_front();
    }
    
};

频率前k个元素

本质就是先用map统计一遍所有数字的出现频率，再放到优先级队列里过一遍，用小顶堆，即队头是最小的，元素大小大于k，就弹出队头，这里用了priority_queue容器，注意下API和compare对象的传参方式（类的函数运算符重载成函数对象），三刷看一下优先级队列里面插入和弹出来元素的时间复杂度和是怎么操作的，是遍历一遍找插入点的方式么。

class Solution {
public:
    class compare {
        public:
        bool operator() (const pair<int,int>& lhs, const pair<int, int>& rhs) {
            //>是小顶堆
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {

        // 要统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }
        //构建小顶堆 优先级队列
        priority_queue<pair<int,int>, vector<pair<int,int>>, compare> que;
        //把频率次数放入小顶堆排序
        for (auto it : map) {
            que.push(it);
            if (que.size() > k) {
                que.pop();
            }
        }
        vector<int> res;
        while (!que.empty()) {
            res.push_back(que.top().first);
            que.pop();
        }
        return res;

    }
};