C++刷剑指offer（面试题59 - I. 滑动窗口的最大值）【滑动窗口】

糖逗

题目出处：leetcode
面试题59 - I. 滑动窗口的最大值
题目描述：

1. 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
   
2. 
   
3. 示例:
   
4. 
   
5. 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
   
6. 输出: [3,3,5,5,6,7]
   
7. 解释:
   
8. 
   
9.   滑动窗口的位置                最大值
   
10. ---------------               -----
    
11. [1  3  -1] -3  5  3  6  7       3
    
12. 1 [3  -1  -3] 5  3  6  7       3
    
13. 1  3 [-1  -3  5] 3  6  7       5
    
14. 1  3  -1 [-3  5  3] 6  7       5
    
15. 1  3  -1  -3 [5  3  6] 7       6
    
16. 1  3  -1  -3  5 [3  6  7]      7
    

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include <deque>
   
4. using namespace std;
   
5. 
   
6. vector<int> solution(vector<int>& input, int k){
   
7.         vector<int> result;
   
8.         deque<int> temp;
   
9.         int front_arrow = 0;
   
10.         if(input.size() == 0 || k == 1) return input;
    
11.         for(int i = 0; i < input.size(); i++){
    
12.                 if(temp.empty()){
    
13.                         temp.push_back(i);
    
14.                         continue;
    
15.                 };
    
16.                 if(input[i] >= input[temp.front()]){
    
17.                         temp.clear();
    
18.                         temp.push_front(i);
    
19.                 }
    
20.                 else{
    
21.                         while(input[i] >= input[temp.back()]){
    
22.                                 temp.pop_back();
    
23.                         }
    
24.                         temp.push_back(i);       
    
25.                 }
    
26.                
    
27.                 while(temp.front() <= i - k){
    
28.                         temp.pop_front();
    
29.                 }
    
30.                 if(i >= k - 1){
    
31.                         result.push_back(input[temp.front()]);
    
32.                 }
    
33.         }
    
34.         return result;
    
35. }
    
36. 
    
37. 
    
38. 
    
39. int main(void){
    
40.         int num;
    
41.     cout << "send vector" << endl;
    
42.     vector<int> list;
    
43.     while(cin >> num)
    
44.     {
    
45.         list.push_back(num);
    
46.     }
    
47.     cout << endl;
    
48.     cout << "send k" <<endl;
    
49.     cin.clear();
    
50.         int k;
    
51.         cin >> k;
    
52.         vector<int> result;
    
53.         result = solution(list, k);
    
54.         for(int i = 0; i < result.size(); i++){
    
55.                 cout << result[i];
    
56.         }
    
57.         cout << endl;
    
58.         return 0;
    
59. }

复制代码

参考链接：
https://www.bilibili.com/video/B ... 1078736512342441171
https://blog.csdn.net/Chnyac/article/details/82710050


注意事项：
1.检查当前最大值是否在滑动窗口内。
2.deque双向队列中存储的是当前值的下标序号。


相同思路的题：面试题59 - II. 队列的最大值

1. 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
   
2. 
   
3. 若队列为空，pop_front 和 max_value&#160;需要返回 -1
   
4. 
   
5. 示例 1：
   
6. 
   
7. 输入:
   
8. ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
   
9. [[],[1],[2],[],[],[]]
   
10. 输出:&#160;[null,null,null,2,1,2]
    
11. 示例 2：
    
12. 
    
13. 输入:
    
14. ["MaxQueue","pop_front","max_value"]
    
15. [[],[],[]]
    
16. 输出:&#160;[null,-1,-1]
    
17. &#160;
    
18. 
    
19. 限制：
    
20. 
    
21. 1 <= push_back,pop_front,max_value的总操作数&#160;<= 10000
    
22. 1 <= value <= 10^5
    
23. 
    

复制代码

1. class MaxQueue {
   
2. public:
   
3.     queue<int> input;
   
4.     deque<int> temp;
   
5.     MaxQueue() {
   
6. 
   
7.     }
   
8.    
   
9.     int max_value() {
   
10.         if(temp.empty()) return -1;
    
11.         else{
    
12.             return temp.front();
    
13.         }
    
14. 
    
15.     }
    
16.    
    
17.     void push_back(int value) {
    
18.         input.push(value);
    
19.         if(temp.empty()) temp.push_back(value);
    
20.         else{
    
21.             if(value >= temp.front()){
    
22.                 temp.clear();
    
23.                 temp.push_front(value);
    
24.             }
    
25.             else{
    
26.                 while(value >= temp.back()){
    
27.                     temp.pop_back();
    
28.                 }
    
29.                 temp.push_back(value);
    
30.             }
    
31.         }
    
32.     }
    
33. 
    
34.     int pop_front() {
    
35.         if(input.empty()) return -1;
    
36.         int result;
    
37.         result = input.front();
    
38.         input.pop();
    
39.         if(result == temp.front()){
    
40.             temp.pop_front();
    
41.         }
    
42. 
    
43.         return result;
    
44.     }
    
45. };
    
46. 
    
47. /**
    
48. * Your MaxQueue object will be instantiated and called as such:
    
49. * MaxQueue* obj = new MaxQueue();
    
50. * int param_1 = obj->max_value();
    
51. * obj->push_back(value);
    
52. * int param_3 = obj->pop_front();
    
53. */

复制代码

相同思路的题：面试题63. 股票的最大利润
题目描述：

1. 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
   
2. 
   
3. &#160;
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: [7,1,5,3,6,4]
   
8. 输出: 5
   
9. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
   
10.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
    
11. 示例 2:
    
12. 
    
13. 输入: [7,6,4,3,1]
    
14. 输出: 0
    
15. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
    
16. 。

复制代码

1. #include<iostream>
   
2. #include<deque>
   
3. #include<vector>
   
4. using namespace std;
   
5. 
   
6. int solution(vector<int>& input){
   
7.         deque<int> temp;
   
8.         if(input.size() == 0) return 0;
   
9.         int compare = 0;
   
10.         for(int i = 0; i < input.size(); i++){
    
11.                 if(temp.empty()) temp.push_back(input[i]);
    
12.                 else{
    
13.                         if(input[i] < temp.back()){
    
14.                                 compare = (temp.front() - temp.back()) > compare ? temp.front() - temp.back() : compare;
    
15.                                 temp.clear();
    
16.                                 temp.push_back(input[i]);
    
17.                         }
    
18.                         if(input[i] > temp.front()){
    
19.                                 temp.push_front(input[i]);
    
20.                         }
    
21.                 }
    
22.                        
    
23.         }
    
24.         compare = (temp.front() - temp.back()) > compare ? temp.front() - temp.back() : compare;
    
25.         return compare;
    
26. 
    
27. }
    
28. 
    
29. 
    
30. 
    
31. int main(void){
    
32.         int number;
    
33.         vector<int> input;
    
34.         int result;
    
35.         while(cin >> number){
    
36.                 input.push_back(number);
    
37.         }
    
38.        
    
39.         result = solution(input);
    
40.         cout << result << endl;
    
41.         return 0;
    
42. }

复制代码

糖逗

这道出题高频

糖逗

剑指 Offer 59 - I. 滑动窗口的最大值（双指针）

1. class Solution {
   
2. public:
   
3.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
   
4.         int left = 0, right = 0;
   
5.         vector<int> res;
   
6.         int len = nums.size();
   
7.         if(len == 0)return res;
   
8.         while(left < len - k + 1){
   
9.             int temp = nums[left];
   
10.             while(right < len && right - left + 1 <= k){
    
11.                 temp = max(temp, nums[right]);
    
12.                 right++;
    
13.             }
    
14.             left++;
    
15.             res.push_back(temp);
    
16.             right = left;
    
17.         }
    
18.         return res;
    
19.     }
    
20. };

复制代码

freeck2013

可以 这道题

糖逗

freeck2013 发表于 2021-10-15 14:14
可以 这道题

谢谢回评！