526互联

代码随想录算法训练营day13| ● 239. 滑动窗口最大值 ● 347.前 K 个高频元素 ● 总结

发布时间 2023-09-18 11:24:37作者: zz子木zz

239.滑动窗口最大值

mydemo--(自己思路)--failed

超出时间限制

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        stack<int> stack;
        int len = nums.size();
        for(int i = 0; i < len - k + 1; i++)
        {
            for(int j = i; j < i + k; j++)
            {
                if(stack.empty())
                    stack.push(nums[j]);
                if(nums[j] > stack.top())
                {
                    stack.pop();
                    stack.push(nums[j]);
                }
            }
            result.push_back(stack.top());
            stack.pop();    //进入下一个窗口之前，先把当前栈清空
        }
        return result;
    }
};

卡哥demo

class Solution {
private:
    class MyQueue{
        public:
            
            deque<int> que;
            
            void pop(int value){
                // 注意判断的顺序，不要操作空队列
                if(!que.empty() && value == que.front()){
                    que.pop_front();
                }
            }

            void push(int value){
                // 注意判断的顺序，不要操作空队列
                while(!que.empty() && value > que.back()){
                    que.pop_back();
                }
                que.push_back(value);
            }

            int getMaxValue(){
                return que.front();
            }
    };

public:
    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.getMaxValue());
        for(int i = k; i < nums.size(); i++){
            que.pop(nums[i - k]);
            que.push(nums[i]);
            result.push_back(que.getMaxValue());
        }
        return result;
    }
};

349. 前K个高频元素

语法难点

思路倒是懂了，但是语法难点太多了

C++ STL priority_queue详解

C++ STL priority_queue自定义排序实现方法详解

C++中 :: 的用法

image-20230918110352997

C++ STL 迭代器 iterator 的用法

/遍历 vector 容器。
#include <iostream>
//需要引入 vector 头文件
#include <vector>
using namespace std;
int main()
{
    vector<int> v{1,2,3,4,5,6,7,8,9,10}; //v被初始化成有10个元素
    cout << "第一种遍历方法：" << endl;
    //size返回元素个数
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] <<" "; //像普通数组一样使用vector容器
    //创建一个正向迭代器，当然，vector也支持其他 3 种定义迭代器的方式
    
       cout << endl << "第二种遍历方法：" << endl;
       vector<int>::iterator i;
    //用 != 比较两个迭代器
    for (i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";
    
       cout << endl << "第三种遍历方法：" << endl;
    for (i = v.begin(); i < v.end(); ++i) //用 < 比较两个迭代器
        cout << *i << " ";
   
       cout << endl << "第四种遍历方法：" << endl;
    i = v.begin();
    while (i < v.end()) { //间隔一个输出
        cout << *i << " ";
        i += 2; // 随机访问迭代器支持 "+= 整数"  的操作
    }
}

运行结果为：

第一种遍历方法：
1 2 3 4 5 6 7 8 9 10
第二种遍历方法：
1 2 3 4 5 6 7 8 9 10
第三种遍历方法：
1 2 3 4 5 6 7 8 9 10
第四种遍历方法：
1 3 5 7 9

卡哥demo

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;
        for(int i = 0; i < nums.size(); i++){
            map[nums[i]]++;
        }

        //定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> 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();
            }
        }

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