生成窗口最大值数组

#include<bits/stdc++.h>
using namespace std;

deque<int> dq;
int main() {
	int n, w;
    cin >> n >> w;
	vector<int> a(n);
    
	for (int i=0; i<n; ++i) {
		cin >> a[i];
	}

	for (int i=0; i<n; ++i) {
		while (!dq.empty() && a[dq.back()] <= a[i]) {
			dq.pop_back();
		}
		dq.push_back(i);
        if (dq.front() == i - w) {
			dq.pop_front();
		}
		if (i >= w-1) {
			cout << a[dq.front()] << ' ';
		}

		
	}

	return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int val;
    struct node *prev;
    struct node *next;
} Node;

Node *createNode(int val);
void addLast(int val);
void removeFirst();

// the head and tail of the double-ended queue
Node *pHead = NULL;
Node *pTail = NULL;

int main(void) {
    int n, w;
    scanf("%d%d", &n, &w);
    int *arr = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }

    int l = 0, r = 0;
    while (r < w) {
        addLast(arr[r++]);
    }

    int index = 0;
    int *res = (int *) malloc((n - w + 1) * sizeof(int));
    for (;;) {
        res[index++] = pHead->val;
        if (arr[l++] == pHead->val)
            removeFirst();
        if (r == n)
            break;
        addLast(arr[r++]);
    }
    // print result
    for (int i = 0; i < index; i++) {
        printf("%d ", res[i]);
    }
    // release memory
    while (pHead != NULL)
        removeFirst();
    free(arr);
    free(res);
    return 0;
}

Node *createNode(int val) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

void addLast(int val) {
    Node *pNode = NULL;
    while (pHead != NULL && val > pTail->val) {
        pNode = pTail;
        if (pHead == pTail) {
            pHead = NULL;
            pTail = NULL;
        } else {
            pTail = pTail->prev;
            pTail->next = NULL;
        }
        free(pNode);
    }
    pNode = createNode(val);
    if (NULL == pHead) {
        pHead = pNode;
        pTail = pNode;
        return;
    }
    pTail->next = pNode;
    pNode->prev = pTail;
    pTail = pNode;
}

void removeFirst() {
    Node *pNode = pHead;
    if (pHead == pTail) {
        pHead = NULL;
        pTail = NULL;
    } else {
        pHead->next->prev = NULL;
        pHead = pHead->next;
    }
    free(pNode);
}

if __name__ == '__main__':
    n, m = map(int, input().strip().split(' '))
    nums = list(map(int, input().strip().split(' ')))
    container = []
    result = []
    for i in range(n):
        # 确保队里的对应index的值是降序排列
        while len(container) > 0 and nums[i] >= nums[container[-1]]:
            container.pop(-1)
        container.append(i)
        # 确保队列里的数都在有效范围内
        while (i - container[0]) >= m:
            container.pop(0)

        if i >= (m - 1):
            # 取出第一个元素，默认就是最大的
            result.append(nums[container[0]])
    print(' '.join([str(ele) for ele in result]))

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, w;
    cin>>n>>w;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    deque<int> Q;
    for(int i=0;i<n;i++){
        while(!Q.empty() && a[Q.back()]<=a[i])
            Q.pop_back();
        Q.push_back(i);
        if(Q.front()==i-w)
            Q.pop_front();
        if(i>=w-1)
            cout<<a[Q.front()]<<' ';
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,w,h=0,t=-1;
    cin>>n>>w;
    vector<int>x(n),res(n,0);
    for(int i=0;i<n;i++)
        cin>>x[i];
    for(int i=0;i<n;i++)
    {
        while(t>=0&&x[res[t]]<x[i])
            t--;
        t++;
        res[t]=i;
        if(i>=w-1&&i<n)
        {
            h=0;
            while(res[h]<i-w+1)
                h++;
            cout<<x[res[h]]<<" ";
        }
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main{

    // 双端队列始终维持一个前大后小的结构，随着窗口右移，队列前面的元素会失效
    // 维护队列：如果队尾对应的元素小，弹出不要；如果队尾对应元素大，就把新的数组的下标加进来，继续维护前大后小的结构
    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        LinkedList<Integer> qMax = new LinkedList<>();
        int[] result = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            // 如果队尾对应的元素比较小，就弹出队尾，直到队尾的位置所代表的值比当前值arr[i]大
            while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[i]) {
                qMax.pollLast();
            }
            qMax.addLast(i);

            // 检查队头下标是否过期，过期就把队头弹出
            if (qMax.peekFirst() == i - w) {
                qMax.pollFirst();
            }
            // 如果窗口出现了，就开始记录每个窗口的最大值
            if (i >= w - 1) {
                result[index++] = arr[qMax.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n;
        int w;
        String line;
        while ((line = br.readLine()) != null) {
            n = Integer.parseInt(line.split(" ")[0]);
            w = Integer.parseInt(line.split(" ")[1]);
            int[] data = new int[n];
            String[] inputHelp = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                data[i] = Integer.parseInt(inputHelp[i]);
            }
            int[] res = getMaxWindow(data,w);
            StringBuilder sb = new StringBuilder();
            for (int i : res){
                sb.append(i).append(" ");
            }
            System.out.println(sb);
        }
    }
}

function getResult(len,winBig,arr){
    let r =[]
    while(arr.length>=winBig){
        r.push(Math.max(...arr.slice(0,winBig)));
        arr.shift();
    }
    return r;
}

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

vector<int> process(const vector<int> &v, int w){
    deque<int> dq;
    vector<int> ans;
    for(int i = 0; i < v.size(); i++){
        while(!dq.empty() && v[dq.back()] <= v[i]){
            dq.pop_back();
        }
        dq.push_back(i);
        if(i >= w && i - w == dq.front())
            dq.pop_front();
        if(i >= w - 1)
            ans.push_back(v[dq.front()]);
    }
    return ans;
}

int main(void){
    int n, w;
    cin >> n >> w;
    vector<int> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];
    vector<int> ans = process(v, w);
    for(auto a : ans)
        cout << a << " ";
    cout << endl;
    return 0;
}

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int n, w, a[N];
int hh, tt, q[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> w;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    
    //max
    tt = -1;
    for (int i = 0; i < n; i ++ ) {
        if (hh <= tt && q[hh] < i - w + 1) hh ++;
        for (; hh <= tt && a[i] > a[q[tt]];) tt --;
        q[++ tt] = i;
        
        if (i - w + 1 >= 0) cout << a[q[hh]] << ' ';
    }    
    return 0;
}

使用双端队列来实现

/*
 * @Description: 生成窗口最大值数组
 * @Author: 
 * @Date: 2020-10-29 14:53:17
 * @LastEditTime: 2020-10-29 15:05:07
 * @LastEditors: Please set LastEditors
 */
#include<iostream>
#include<vector>
#include<deque>
using namespace std;

int main(){

    int n, w;
    cin >> n >> w;
    vector<int> arr(n);
    for(int i = 0;i < n;i++){
        cin >> arr[i];
    }
    deque<int> dq;
    for(int i = 0;i < n;i++){
        // 保证双端队列是一个递减的序列， 队尾的表示的值小于等于当前遍历的值，则队尾弹出，循环判断。
        while(!dq.empty() && arr[dq.back()] <= arr[i]){
            dq.pop_back();
        }
        dq.push_back(i);
        // 如果当前队头==i-w 表示当前队头已经过期，则弹出队头
        if(dq.front() == i - w){
            dq.pop_front();
        }
        // 求出当前队头的最大值
        if(i >= w - 1){
            cout << arr[dq.front()] << " ";
        }
    }
    system("pause");
    return 0;
}

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

int main(){
    int n,w;
    deque<int> dq;
    vector<int> vec;
    cin>>n>>w;
        int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        if(dq.size()==0)
            dq.push_back(i);
        else{
            if(i-dq.front()>w-1){
                dq.pop_front();
            }
            while(dq.size()!=0&&a[i]>a[dq.back()]){
                dq.pop_back();
            }
            dq.push_back(i);
            if(i>=w-1){
                vec.push_back(a[dq.front()]);
            }
        }
    }
    for(auto i:vec){
        cout<<i<<" ";
    }
    return 0;
    
}

# 利用python中List 模拟 双端队列
N, w = list(map(int, input().split()))
nums = list(map(int, input().split()))

queue = []
res = []
for i in range(N):
    while len(queue)>0 and nums[i] > nums[queue[-1]]:
        queue.pop()
    queue.append(i)
    if queue[0] == i - w:
        queue.pop(0)
    if i >= w-1 and len(queue) > 0:
        res.append(nums[queue[0]])
result = ''
for i in range(len(res)-1):
    result += str(res[i])
    result += ' '
result += str(res[-1])
print(result)