代码随想录算法训练营第13天 |239.滑动窗口最大值、347.前 K 个高频元素

239. 滑动窗口最大值 - 力扣（LeetCode）

思路:我是用map过的这道题，内存消耗和执行用时都花了很久，如下图(只击败了％5)，万分惭愧!因为map有自动排序，所以我直接先录入k个数字，然后将最大值存入结果数组，循环遍历，每次都移除最后一个元素并且添加新的元素(记得要把map中value为0的元素移除)，然后直接把最大的加入结果数组，遍历完成一遍以后就是最终答案了

• 这道题过得很狼狈，属于是抖机灵法，栈与队列专题居然用了map

• 万万没想到，第一道Hard竟然是这样过的

  

  • 下面说一下这道题的正解：应该使用单调队列，具有的功能是push的时候如果队列为空，直接添加值到尾端，如果非空，则判断是否比尾端元素大，如果比它大就移除该元素，直到队列为空或者找到比它大的数值，此时再把值添加到尾端，即push_back;接下来就是pop的功能，移除元素时判断要移除的元素是不是首端最大的元素，如果是就进行移除，否则不操作;还要实现front的功能，直接输出队列前端第一个元素就可以了。构造完这样的单调队列以后，先遍历k个元素，执行push操作，接着将首端最大的元素赋给结果数组，然后再遍历剩下的数组元素，每次移动一位，按顺序执行pop、push,添加首端最大的元素给结果数组即可。下图是正解的速度，所以此题还是强烈建议使用单调队列解法

    

我的AC代码

//时间复杂度O(nlogn),空间复杂度O(k)
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        map<int, int> mp;
        vector<int> ans;
        int nsize = nums.size();
        for(int i = 0; i < k; ++i) {
            mp[nums[i]]++;
        }
        auto iter1 = mp.end();
        iter1--;
        ans.push_back(iter1->first);
        for(int i = k; i < nsize; ++i) {
            mp[nums[i - k]]--;
            if(mp[nums[i - k]] == 0) {
                mp.erase(nums[i - k]);
            }
            mp[nums[i]]++;
            iter1 = mp.end();
            iter1--;
            ans.push_back(iter1->first);
        }
        return ans;
    }
};

复刻标准答案

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int nsize = nums.size();
        vector<int> results;
        myQueue mq;
        for(int i = 0; i < k; ++i) {
            mq.push(nums[i]);
        }
        results.push_back(mq.front());
        for(int i = k; i < nsize; ++i) {
            mq.pop(nums[i - k]);
            mq.push(nums[i]);
            results.push_back(mq.front());
        }
        return results;
    }
private:
    class myQueue {
    public:
        myQueue() {

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

        void pop(int x) {
            if(dq.front() == x) {
                dq.pop_front();
            }
        }

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

    private:
        deque<int> dq;
    };
};

标准答案

//时间复杂度O(n),空间复杂度O(k)
class Solution {
private:
    class MyQueue { //单调队列（从大到小）
    public:
        deque<int> que; // 使用deque来实现单调队列
        // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
        // 同时pop之前判断队列当前是否为空。
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        // 如果push的数值大于入口(即队列后端)元素的数值
        // 那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int value) {
            while (!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);

        }
        // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
        int front() {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
            que.push(nums[i]);
        }
        result.push_back(que.front()); // result 记录前k的元素的最大值
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]); // 滑动窗口移除最前面元素
            que.push(nums[i]); // 滑动窗口前加入最后面的元素
            result.push_back(que.front()); // 记录对应的最大值
        }
        return result;
    }
};

347. 前 K 个高频元素 - 力扣（LeetCode）

思路:这题我还是用map写的，十分惭愧……遍历数组，把值都map中，记录每个值出现的个数，接着再把map中的值传入vector，然后让vector按照value降序排序，将该vector<PAIR>的前k个赋值给vector<int>并且返回即可

• 看了一下标准答案，发现与我的答案整体思想上是一致的，不过我这里用的是vector<PAIR>配合sort直接排序，而标准答案则用的是优先队列priority_queue,时间复杂度上标准答案更胜一筹。因为我是排序所有n个元素，而标准答案只排序k个元素，但在LeetCode实际运行中二者运行时间一致(主要是LeetCode的耗时不怎么准)
• 简要说一下标准答案的思路：首先也是让map统计出现频率，然后用小顶堆(即头部为最大值的优先队列)来处理k个最大的元素。具体处理过程是，先push值进小顶堆，如果小顶堆的size大于k个，那么就把头部弹出，如此一来，把所有小的都弹出去了，剩下k个不就是最大的了吗？只不过最后取值的时候要倒着取而已。所以我们遍历一遍map，用小顶堆处理所有数据，最后再把小顶堆中的数据按照倒序赋给结果数组，返回结果数组即可
• 我们在写快排以及其他正常sort的cmp函数的时候，return left > right是从大到小，return left < right是从小到大，而优先队列则正好反过来，return left > right是从小到大，return left < right是从大到小

我的AC代码

使用unordered_map

//时间复杂度O(nlogn), 空间复杂度O(n)
class Solution {
public:
    typedef pair<int, int> PAIR;
    struct cmpByValue {
        bool operator()(const PAIR& v1, const PAIR& v2) {
            return v1.second > v2.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int nsize = nums.size();
        unordered_map<int, int> mp;
        vector<int> ans;
        for(int i = 0; i < nsize ; ++i) {
            mp[nums[i]]++;
        }
        vector<PAIR> vp(mp.begin(), mp.end());
        sort(vp.begin(), vp.end(), cmpByValue());
        for(int i = 0; i < k; ++i) {
            ans.push_back(vp[i].first);
        }
        return ans;
    }
};

复刻标准答案

//时间复杂度O(nlogk), 空间复杂度O(n)
class Solution {
public:
    typedef pair<int, int>PAIR;
    class comByValue{
    public:
        bool operator()(const PAIR& pr1, const PAIR& pr2) {
            return pr1.second > pr2.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ans(k);
        unordered_map<int, int> mp;
        for(auto a : nums) {
            mp[a]++;
        }
        priority_queue<PAIR, vector<PAIR>, comByValue> pr_q;
        for(auto it : mp) {
            pr_q.push(it);
            if(pr_q.size() > k) {
                pr_q.pop();
            }
        }
        for(int i = k - 1;i >= 0; --i) {
            ans[i] = pr_q.top().first;
            pr_q.pop();
        }
        return ans;
    }
};

标准答案

// 时间复杂度：O(nlogk), 空间复杂度：O(n)
class Solution {
public:
    // 小顶堆
    class mycomparison {
    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]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆，扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};

额外题目

71. 简化路径 - 力扣（LeetCode）

思路:一道模拟题，但有点复杂，主要得把握好..和.的处理方法，即要把返回上一层与本目录这两个命令和普通目录名或者文件名区分开来，以及一些特殊情况如/../的处理，还有当最后一个路径是普通文件，即最后没有/时要记得补上，具体内容可以看代码，说实话写的有点乱0.0

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    string simplifyPath(string path) {
        path += "/";
        int psize = path.size();
        stack<char> st;
        string ans = "";
        st.push('/');
        int cnt = 0;
        int other = 0;
        for(int i = 0; i < psize; ++i) {
            st.push(path[i]);
            if(path[i] == '.') {
                cnt++;
            }
            else if(path[i] != '/'){
                other++;
            }
            if(path[i] == '/') {
                while(!st.empty() && st.top() == '/') {
                    st.pop();
                }
                if(cnt == 1 && other == 0) {
                    st.pop();
                } 
                else if(cnt == 2 && other == 0) {
                    st.pop();
                    st.pop();
                    st.pop();
                    if(st.empty()) {
                        st.push('/');
                    }
                    while(!st.empty() && st.top() != '/') {
                        st.pop();
                    }
                }
                else {
                    st.push('/');
                }
                cnt = 0;
                other = 0;
            }
        }
        if(!st.empty() && st.top() == '/') {
            st.pop();
        }
        if(st.empty()) {
            st.push('/');
        }
         while(!st.empty()) {
            ans += st.top();
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};