刷题笔记day13

239.滑动窗口最大值

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

自己构造MyQueue的逻辑没有理顺。
pop()中条件是if不是while，只用删除一次而不是像front中一样需要进行排序所以while循环。

自己写的代码

参照题解写的代码：

class Solution {
public:
    class Myqueue {
    public:
        void pop(int x) {
            if (! deq.empty() && x == deq.front()) {
                deq.pop_front();
            }
        }

        void push(int x) {
            while (! deq.empty() && x > deq.back()) {
                deq.pop_back();
            }
            deq.push_back(x);
        }

        int front() {
            return deq.front();
        }

    private:
        deque<int> deq;
    };

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        Myqueue que;
        vector<int> result;
        for (int i = 0; i < k; ++i) {
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for (int j = k; j < nums.size(); ++j) {
            que.pop(nums[j-k]);
            que.push(nums[j]);
            result.push_back(que.front());
        }
        return result;
    }
};

看了题解后的收获

滑动窗口法——构造自己的queue。

347.前K个高频元素

文章讲解：代码随想录
是否自己做出来通过全部用例：否

自己写的代码

看了题解后写的代码：

class Solution {
public:
    class mycomparison {
    public:
        bool operator() (const pair<int, int> pair1, const pair<int, int> pair2) {
            return pair1.second > pair2.second;
        } 
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> umap;
        for (int i = 0; i < nums.size(); ++i) {
            ++umap[nums[i]];
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pque;
        for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
            pque.push(*iter);
            if (pque.size() > k) {
                pque.pop();
            }
        }
        vector<int> result(k);
        for (int i = k - 1; i >= 0; --i) {
            result[i] = pque.top().first;
            pque.pop();
        }
        return result;
    }
};

看了题解后的收获

掌握了优先队列这个容器适配器。
优先级队列：披着队列外皮的堆。
缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

栈与队列总结

文章讲解：代码随想录：