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

糖逗

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

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

#include <iostream>
#include <vector>
#include <deque> 
using namespace std;

vector<int> solution(vector<int>& input, int k){
        vector<int> result;
        deque<int> temp;
        int front_arrow = 0;
        if(input.size() == 0 || k == 1) return input;
        for(int i = 0; i < input.size(); i++){
                if(temp.empty()){
                        temp.push_back(i);
                        continue;
                };
                if(input[i] >= input[temp.front()]){
                        temp.clear();
                        temp.push_front(i);
                }
                else{
                        while(input[i] >= input[temp.back()]){
                                temp.pop_back(); 
                        }
                        temp.push_back(i);        
                }
                
                while(temp.front() <= i - k){
                        temp.pop_front();
                }
                if(i >= k - 1){
                        result.push_back(input[temp.front()]);
                }
        }
        return result;
}



int main(void){
        int num;
    cout << "send vector" << endl;
    vector<int> list;
    while(cin >> num)
    {
        list.push_back(num);
    }
    cout << endl;
    cout << "send k" <<endl;
    cin.clear();
        int k;
        cin >> k;
        vector<int> result;
        result = solution(list, k);
        for(int i = 0; i < result.size(); i++){
                cout << result[i];
        }
        cout << endl;
        return 0;
}

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


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


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

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]
 

限制：

1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

class MaxQueue {
public:
    queue<int> input;
    deque<int> temp;
    MaxQueue() {

    }
    
    int max_value() {
        if(temp.empty()) return -1;
        else{
            return temp.front();
        }

    }
    
    void push_back(int value) {
        input.push(value);
        if(temp.empty()) temp.push_back(value);
        else{
            if(value >= temp.front()){
                temp.clear();
                temp.push_front(value);
            }
            else{
                while(value >= temp.back()){
                    temp.pop_back();
                }
                temp.push_back(value);
            }
        }
    }

    int pop_front() {
        if(input.empty()) return -1;
        int result;
        result = input.front();
        input.pop();
        if(result == temp.front()){
            temp.pop_front();
        }

        return result;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

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

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

 

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
。

#include<iostream>
#include<deque>
#include<vector>
using namespace std;

int solution(vector<int>& input){
        deque<int> temp;
        if(input.size() == 0) return 0; 
        int compare = 0;
        for(int i = 0; i < input.size(); i++){
                if(temp.empty()) temp.push_back(input[i]);
                else{
                        if(input[i] < temp.back()){
                                compare = (temp.front() - temp.back()) > compare ? temp.front() - temp.back() : compare;
                                temp.clear();
                                temp.push_back(input[i]); 
                        }
                        if(input[i] > temp.front()){
                                temp.push_front(input[i]);
                        }
                }
                        
        }
        compare = (temp.front() - temp.back()) > compare ? temp.front() - temp.back() : compare;
        return compare;

} 



int main(void){
        int number;
        vector<int> input;
        int result;
        while(cin >> number){
                input.push_back(number);
        } 
        
        result = solution(input);
        cout << result << endl;
        return 0;
}

糖逗

这道出题高频

糖逗

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

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int left = 0, right = 0;
        vector<int> res;
        int len = nums.size();
        if(len == 0)return res;
        while(left < len - k + 1){
            int temp = nums[left];
            while(right < len && right - left + 1 <= k){
                temp = max(temp, nums[right]);
                right++;
            }
            left++;
            res.push_back(temp);
            right = left;
        }
        return res;
    }
};

freeck2013

可以 这道题

糖逗

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

谢谢回评！