1 题目描述

　　给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

2 思路和方法

　　（1）使用int max_number =*max_element(num.begin()+i,num.begin()+size+i);语句找到最大值，int count = num.size()-size+1;　　vector<int> result; 　　result. push_back(max_number)。

　　（2）用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次。a.判断当前最大值是否失效，即不在滑动窗口内；b.新增加的值从队尾开始比较，把所有比他小的值丢掉。

　　

3 C++核心

（1）

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        int count = num.size()-size+1;
        vector<int> result;
        if(size==0 || num.size()==0){
            return result;
        }
        for(int i =0;i<count;i++){
            int max_number = *max_element(num.begin()+i,num.begin()+size+i);
            result.push_back(max_number);
        }
        return result;
    }
};

（2）

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> resu;
        if (num.size() >= size && size >= 1) {
            deque<int> numDeque;
            //首先把前size个数按照规则压入双向队列
            for (int i = 0; i != size; i++) {
                while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {
                    numDeque.pop_back();    //后面加入的数据大于队列中的数据时，队列中的数据依次弹出
                }
                numDeque.push_back(i);
            }
            //压入第一个最大值
            //滑动窗口的最大值总是位于双向队列的头部
            resu.push_back(num[numDeque.front()]);
            for (int i = size; i != num.size(); i++) {
                //首先按照规则压入新的值
                while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {
                    numDeque.pop_back();    //后面加入的数据大于队列中的数据时，队列中的数据依次弹出
                }
                //并且删除旧值，即滑出了窗口的值
                if (!numDeque.empty() && numDeque.front() <= static_cast<int>(i - size)) {
                    numDeque.pop_front();
                }
                numDeque.push_back(i);
                resu.push_back(num[numDeque.front()]);
            }
        }
        return resu;
    }
};

4 C++完整代码

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> maxInWindows(const vector<int>& num, unsigned int size);
int main() {
    vector<int> data{ 2, 3, 4, 2, 6, 2, 5, 1 };
    vector<int> resu = maxInWindows(data, 3);
    for (auto a : resu) {
        cout << a << endl;
    }
    system("pause");
    return 0;
}
vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
    vector<int> resu;
    if (num.size() >= size && size >= 1) {
        deque<int> numDeque;
        //首先把前size个数按照规则压入双向队列
        for (int i = 0; i != size; i++) {
            while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {
                numDeque.pop_back();
            }
            numDeque.push_back(i);
        }
        //压入第一个最大值
        //滑动窗口的最大值总是位于双向队列的头部
        resu.push_back(num[numDeque.front()]);
        for (int i = size; i != num.size(); i++) {
            //首先按照规则压入新的值
            while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {
                numDeque.pop_back();
            }
            //并且删除旧值，即滑出了窗口的值
            if (!numDeque.empty() && numDeque.front() <= static_cast<int>(i - size)) {
                numDeque.pop_front();