有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置，求每一种窗口状态下的最大值。（如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值）
[编程题]生成窗口最大值数组
- 热度指数：7211 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行输入n和w，分别代表数组长度和窗口大小第二行输入n个整数，表示数组中的各个元素
输出描述:
输出一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值
示例1
输入
8 3 4 3 5 4 3 3 6 7
输出
5 5 5 4 6 7
说明
例如，数组为[4，3，5，4，3，3，6，7]，窗口大小为3时：
[4 3 5] 4 3 3 6 7 窗口中最大值为5
4 [3 5 4] 3 3 6 7 窗口中最大值为5
4 3 [5 4 3] 3 6 7 窗口中最大值为5
4 3 5 [4 3 3] 6 7 窗口中最大值为4
4 3 5 4 [3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7
输出的结果为{5 5 5 4 6 7}
备注:
#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;
}
发表于 2019-10-26 19:04:37
回复(1)
#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);
}
发表于 2022-07-14 22:48:35
回复(0)
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]))
发表于 2021-04-25 14:36:05
回复(0)
#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;
}
发表于 2020-02-09 01:33:34
回复(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;
}
发表于 2019-08-25 20:41:46
回复(0)
这题java的同学若用java自带的双向链表（LinkedList）会超时过不了，改用数组即可。
代码如下：
static int[] getMaxWindow(int[] arr, int w) {
if(arr==null||arr.length==0||w<1){
return null;
}
int[] res = new int[arr.length-w+1];
int idx = 0;
int[] qList = new int[arr.length];
//r为有效区域右边界，代表原来双向链表的尾部位置
int r =0 ;
//l为有效区域左边界，代表原来双向链表的头部位置
int l = 0;
//qList 里有效元素的数量，代表原双向链表里的size()
int count =0;
for(int i =0;i<arr.length;i++){
while(count!=0&&r>0&&arr[i]>=arr[qList[r-1]]&&r>=l){
//设置成-1表示失效，即相当于原来的双向链表里的pollLast()方法
qList[r-1]=-1;
r--;
count--;
}
//从尾部加元素，相当于原双向链表里的addLast()
qList[r]=i;
count++;
r++;
if(arr==null||arr.length==0||w<1){
return null;
}
int[] res = new int[arr.length-w+1];
int idx = 0;
int[] qList = new int[arr.length];
//r为有效区域右边界，代表原来双向链表的尾部位置
int r =0 ;
//l为有效区域左边界，代表原来双向链表的头部位置
int l = 0;
//qList 里有效元素的数量，代表原双向链表里的size()
int count =0;
for(int i =0;i<arr.length;i++){
while(count!=0&&r>0&&arr[i]>=arr[qList[r-1]]&&r>=l){
//设置成-1表示失效，即相当于原来的双向链表里的pollLast()方法
qList[r-1]=-1;
r--;
count--;
}
//从尾部加元素，相当于原双向链表里的addLast()
qList[r]=i;
count++;
r++;
if(qList[l]==i-w){
//左边界右移一位，有效区域减少一位元素，相当于原双向链表里的pollFirst()
qList[l++]=-1;
count--;
}
if(i>=w-1){
res[idx++] = arr[qList[l]];
}
}
return res;
编辑于 2019-08-09 22:16:59
回复(0)
单调队列的应用，遍历数组，维护一个队头到队尾元素单调递减的双端队列（存下标，不存具体数值）。(1) 如果当前元素比队尾小，直接从队尾入队，否则不断将元素从队尾弹出，直到当前元素可以入队；(2) 如果当前窗口头部的元素为单调队列的头部元素，要加入此时的元素 i 就必须先从头部把窗口左边界的数弹出再将 i 从队尾加入，表示窗口向右滑动了一步。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]), w = Integer.parseInt(params[1]);
params = br.readLine().split(" ");
int[] arr = new int[n];
for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(params[i]);
LinkedList<Integer> qmax = new LinkedList<>();
int index = 0;
for(int i = 0; i < n; 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) System.out.print(arr[qmax.peekFirst()] + " ");
}
}
}
发表于 2021-11-17 23:39:52
回复(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);
}
}
}
发表于 2020-04-05 13:42:01
回复(0)
维护一个单调递增队列，不断pop出队尾的小元素，弹出队头的最大元素
#include <bits/stdc++.h>
using namespace std;
// 单调递增的单调队列
deque<int> dq;
void push_min(int val){
while(!dq.empty() && dq.back() < val){
dq.pop_back();
}
dq.push_back(val);
}
void pop_min(int val){
if(!dq.empty() && dq.front() == val){
dq.pop_front();
}
}
int getMax(){
return dq.front();
}
int main()
{
int n, w;
cin >> n >> w;
vector<int> nums(n);
for(int i = 0; i < n; ++i) cin >> nums[i];
for(int i = 0; i < w; ++i){
push_min(nums[i]);
}
vector<int> result;
result.push_back(getMax());
for(int i = w; i < n; ++i){
push_min(nums[i]);
pop_min(nums[i - w]);
result.push_back(getMax());
}
for(auto &c : result){
cout << c << " ";
}
return 0;
}
发表于 2022-04-07 15:44:51
回复(0)
单调队列，双向队列，队列递减，如果小于等于队列最后元素，直接放进去，如果大于，将最后的弹出放进去，因为上一个元素不再需要。如果最前面的元素是要去掉的元素，则最前面元素删去。
#include "bits/stdc++.h"
using namespace std;
int main()
{
int n;cin>>n;
int w;cin>>w;
vector<int> nums(n);
for(int i=0;i<n;i++)cin>>nums[i];
deque<int> que;
//int max_ret=nums[0];
for(int i=0;i<w;i++)
{
if(que.size()==0||que.back()>=nums[i]) que.push_back(nums[i]);
else {
while(!que.empty()&&que.back()<nums[i])que.pop_back();
que.push_back(nums[i]);
}
}
cout<<que.front()<<' ';
for(int i=w;i<n;i++)
{
if(que.size()==0||que.back()>=nums[i]) que.push_back(nums[i]);
else {
while(!que.empty()&&que.back()<nums[i])que.pop_back();
que.push_back(nums[i]);
}
if(que.front()==nums[i-w])que.pop_front();
cout<<que.front()<<' ';
}
return 0;
}
发表于 2022-02-10 15:42:59
回复(0)
用一个队列存储窗口内的最大值的坐标
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int w = in.nextInt();
int[] nums = new int[n];
int i = 0;
while (in.hasNext()) {
nums[i++] = in.nextInt();
}
int[] res = new Main().maxWindow(nums, w);
for (int num : res) {
System.out.print(num + " ");
}
}
public int[] maxWindow(int[] nums, int w) {
int n = nums.length;
if (nums == null || n == 0 || w <= 1) return nums;
int size = n - w + 1;
int[] res = new int[size];
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
if (queue.peekFirst() <= i - w) {
queue.pollFirst();
}
if (i + 1 >= w) {
res[i + 1 - w] = nums[queue.peekFirst()];
}
}
return res;
}
}
发表于 2021-07-31 13:01:14
回复(0)
今天吃【超久才做出来】
let line=readline()
let wSize=parseInt(line.split(' ')[1])
line=readline()
var arr=line.split(' ').map(item=>parseInt(item))
var res=[]
if(arr.length<=wSize){
res.push(Math.max(...arr))
console.log(res.join(' '))
}
let left=0,right=0
let subarr=[]
while(right<arr.length){
if(left&&arr[left-1]==subarr[0]){
subarr.shift()
}
if(arr[right]>=subarr[0]){
subarr=[arr[right]]
}else{
while(subarr[subarr.length-1]<arr[right]){
subarr.pop()
}
subarr.push(arr[right])
}
right++
if(right>=wSize){res.push(subarr[0]),left++}
}
console.log(res.join(' '))
发表于 2021-06-25 15:58:53
回复(0)
#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;
}
本题是一个窗口问题的简化版。
实际是求窗口中最大值是有套路的
使用双端队列来求解。
发表于 2021-05-28 15:22:19
回复(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;
}
发表于 2020-12-06 14:35:57
回复(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;
}
发表于 2020-10-29 15:06:22
回复(0)
真就时间不行呗，难受
import java.util.Queue;
import java.util.LinkedList;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main{
private Queue<Integer> queue;
public Main(){
this.queue = new LinkedList<Integer>();
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
Main m = new Main();
String[] s1 = bf.readLine().split(" ");
int forLength = Integer.valueOf(s1[0]);
int windowLength = Integer.valueOf(s1[1]);
int[] result = new int[forLength-windowLength+1];
String[] s2 = bf.readLine().split(" ");
int[] array = new int[forLength];
for(int i=0;i<forLength;i++){
array[i] = Integer.valueOf(s2[i]);
}
m.windows(array,result,windowLength);
String out = "";
for(int j = 0;j<forLength-windowLength+1;j++){
int value = m.queue.poll();
out = out + value+ " ";
}
System.out.println(out);
}
public void windows(int[] array,int[] result,int windowlength){
int max = array[0];
for(int i=0;i<array.length-windowlength+1;i++){
max = array[i];
for (int j=i;j<windowlength+i;j++){
max = max>array[j]?max:array[j];
}
this.queue.offer(max);
}
}
}
发表于 2020-01-13 21:49:24
回复(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;
}
发表于 2020-01-05 08:18:33
回复(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)
发表于 2019-08-24 11:29:32
回复(0)
就是一道扣边界的题
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int w = sc.nextInt();
int[] x = new int[n];
for (int i = 0; i < n; i++){
x[i] = sc.nextInt();
}
if (n == 0) {
System.out.print("");
return;
}
int[] res = getMax(x, w);
for (int i = 0; i < res.length; i++){
System.out.print(res[i] + " ");
}
}
private static int[] getMax(int[] x, int w){
int len = x.length;
if (w == 1) return x;
int[] arr = new int[len - w + 1];
int left = 0;
int right = left + w - 1;
if (right >= len - 1) {
arr[0] = maxValue(x, left, len - 1);
return arr;
}
int i = 0;
int index = maxValue(x, left, right);
int pre = left;
left++;
right++;
arr[i++] = x[index];
while (right <= len-1){
if (index == pre){
index = maxValue(x, left, right);
arr[i++] = x[index];
} else {
if (x[index] < x[right]){
index = right;
arr[i++] = x[right];
} else {
arr[i++] = x[index];
}
}
left++;
right++;
if (index < left && right <= len-1){
index = maxValue(x, left, right);
}
}
return arr;
}
private static int maxValue(int[] x, int left, int right){
if (left == right) return x[left];
int maxValue = x[left];
int index = left;
while (left <= right){
if (x[left] > maxValue){
maxValue = x[left];
index = left;
}
left++;
}
return index;
}
}
发表于 2019-08-22 16:27:56
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-08 14:42:03
-
2023-03-06 14:56:00
-
2023-03-04 00:53:26
-
2023-02-16 23:50:09
-
2023-02-10 10:03:53
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
