239. 滑动窗口最大值

题目链接:https://leetcode.cn/problems/sliding-window-maximum/

看到题目的第一个想法:想到的使用暴力法把每一种情况给算出来,但是显然这样会超时

看完代码随想录后的想法:了解到了单调队列这种数据结构(也是一种自己可以实现的数据结构)

比较重要的是其函数的实现,一开始并不能理解,后面自己思考以后能够理解

pop函数:用来弹出不断改变的窗口的之前那一个值

这个pop函数只维护front 因为其他值是由push函数来删除的

push函数:

不仅是放入新的值,并且把前面比当前value小的数全给删掉,这样保证front一定是最大值

 1     #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 class Solution
 5 {
 6 private:
 7     class myqueue
 8     {
 9     public:
10         // front用来维护最大值
11         // 用来删除滑动窗口的第一个数组
12         void pop(int value)
13         {
14             if (!que.empty() && value == que.front())
15             {
16                 que.pop_front();
17             }
18         }
19         void push_back(int value)
20         {
21             while (!que.empty() && value > que.back())
22             {
23                 que.pop_back();
24             }
25             que.push_back(value);
26         }
27         int getfront()
28         {
29             return que.front();
30         }
31 
32     private:
33         deque<int> que;
34     };
35 
36 public:
37     vector<int> maxSlidingWindow(vector<int> &nums, int k)
38     {
39         myqueue que;
40         for (int i = 0; i < k; i++)
41         {
42             que.push_back(nums[i]);
43         }
44         vector<int> result;
45         result.push_back(que.getfront());
46         for (int i = k; i < nums.size(); i++)
47         {
48             que.pop(nums[i - k]);
49             que.push_back(nums[i]);
50             result.push_back(que.getfront());
51         }
52         return result;
53     }
54 };

347.前 K 个高频元素

题目链接:https://leetcode.cn/problems/top-k-frequent-elements/

看到代码随想录的第一想法:第一想法用hashmap 然后排序取前两个,但是qsort的时间复杂度nlogn,与题目要求不符合

看代码随想录后的想法:用优先级队列,用小顶堆,把小的排在前面,然后设置维护的个数位k,这样就能把big o降道 n logk.

学会了优先级队列的构造使用.

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 class Solution
 5 {
 6 private:
 7     class myqueue
 8     {
 9     public:
10         // front用来维护最大值
11         // 用来删除滑动窗口的第一个数组
12         void pop(int value)
13         {
14             if (!que.empty() && value == que.front())
15             {
16                 que.pop_front();
17             }
18         }
19         void push_back(int value)
20         {
21             while (!que.empty() && value > que.back())
22             {
23                 que.pop_back();
24             }
25             que.push_back(value);
26         }
27         int getfront()
28         {
29             return que.front();
30         }
31 
32     private:
33         deque<int> que;
34     };
35 
36 public:
37     vector<int> maxSlidingWindow(vector<int> &nums, int k)
38     {
39         myqueue que;
40         for (int i = 0; i < k; i++)
41         {
42             que.push_back(nums[i]);
43         }
44         vector<int> result;
45         result.push_back(que.getfront());
46         for (int i = k; i < nums.size(); i++)
47         {
48             que.pop(nums[i - k]);
49             que.push_back(nums[i]);
50             result.push_back(que.getfront());
51         }
52         return result;
53     }
54 };

用了挺长时间来学习相关的数据结构 已累麻了~