视频课单调队列求区间最小值的问题

讨论

全局板块

我的问题

void push(int x) {
	while(head < tail && a[q[head]] > a[x] )
		head++;
	q[tail++] = x;
}

为什么只比较队头元素和新插入元素然后弹出队头呢？
假如输入数据是1 5 4 3 2
滑动的区间为3
那么按照讲义上的程序运行出来，结果是1 5 2
是不符合区间的最小值的。
那么请问老师，是不是标程有错，或者是我对题目理解错误？

下面是按照讲义的程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>

typedef long long ll;

const int N=100;

int q[N], head, tail, a[N];
int n, k;

void push(int x) {
	while(head < tail && a[q[head]] > a[x] )
		head++;
	q[tail++] = x;
}

void pop_front(int x) {
	while(head < tail && q[head] < x)
		head++;
}

int main() {
	scanf("%d %d",&n,&k);
	for(int i = 1;i <= n;i++) {
		scanf("%d", &a[i]);
	}
	
	for(int r = 1;r <= n;r++) {
		push(r);

		if(r >= k) {
			int l = r - k + 1;
			pop_front(l);
			printf("%d\n", a[q[head]]);
		}
	}
	
 	return 0;
}

Showson

2019-08-25 14:18:39

在队尾的插入和单调栈一样，所以代码对应的正确代码应为

void push(int x) {
	while(head < tail && a[q[tail-1]] > a[x] )
		tail--;
	q[tail++] = x;
}

Showson

2019-08-25 3:10:54

感谢你的反馈对这里写错了应该从队尾删除这是我的疏忽我当时写完以后试了一些小数据发现可以得到正确答案就以为没问题了大家写代码的时候也要注意这个问题哦具体的代码我白天给大家发出来

我的问题

共 2 条回复