A?Sliding Window（POJ - 2823）

（单调队列）
题目链接

本题维护两个单调队列就可以了
在求窗口内最大值时，需要我们维护一个单调递减的队列，队头所对应的元素永远是最大的，只有在当前位置到队头位置长度超过窗口长度时，才将队头弹出，在维护递减性时，如果当前位置所对应元素比队尾所对应元素要大，那么弹出队尾，直到队空或者找到一个比当前位置所对应元素大的。
而求窗口最小值时反之就行

在POJ交的时候交C++，不要交G++

代码

#include <cstdio>
const int M = 1000010;
int num[M], min1[M], max1[M], que1[M], que2[M];	
int n, m;
void find_min() {
	int l = 1, r = 0, cnt = 0;
	for (int i = 1; i <= n; ++i) {
		while (l <= r && i - que1[l] + 1 > m) l++;
		while (l <= r && num[i] <= num[que1[r]]) r--;	
		que1[++r] = i;
		if (i < m) continue;
		min1[++cnt] = num[que1[l]];
	}
	for (int i = 1; i <= cnt; ++i) printf("%d ", min1[i]); printf("\n");
}
void find_max() {
	int l = 1, r = 0, cnt = 0;
	for (int i = 1; i <= n; ++i) {
		while (l <= r && i - que2[l] + 1 > m) l++;
		while (l <= r && num[i] >= num[que2[r]]) r--;
		que2[++r] = i;
		if (i < m) continue;
		max1[++cnt] = num[que2[l]];
	}
	for (int i = 1; i <= cnt; ++i) printf("%d ", max1[i]); printf("\n");
}
int main() {

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &num[i]);
	find_min(); find_max();
	return 0;
}

B?Bad Hair Day （POJ - 3250）

(单调队列)
题目链接

本题维护一个单调递减的单调对列就可以，如果当前位置对应元素大于等于队头元素那么弹出队头元素，直到找到第一个严格大于当前位置对应元素停下。每次队内元素长度 - 1 也就是r - l，也就是其他能看到当前新加入的牛的数量，所以每次加r - l。

#include <cstdio>
#define ll long long 
const int M = 80080;
int n;
int num[M], que[M];
void Solve() {
	int l = 1, r = 0;
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		while (l <= r && num[i] >= num[que[r]]) r--;
		que[++r] = i;
		if (r > l) ans += r - l;
	}
	printf("%lld", ans);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &num[i]);
	Solve();
	return 0;
}

C?Largest Rectangle in a Histogram (POJ - 2559)’

（单调栈）

题目链接

本题可以维护一个单调栈，每次新进入一个矩形如果高度大于栈顶，则入队，如果小于等于栈顶则证明栈顶的矩形的高度不可能超过当前要新进入的矩形也就是栈顶矩形的右边界已经确定，则已经可以开始计算栈顶矩形的高度，因为单调栈是逐渐上升的，那么左边不可能超过栈内栈顶之下的元素，所以左边界为栈内栈顶之下的元素的位置。左右边界都可以确定，那么宽度就可以确定，而高度为栈顶矩形的高度。最后每次出一个栈顶元素，求一次面积最大值。
最后要注意，求到第n + 1个元素，将n + 1个矩形高度设置为0，让栈内所有未求出的矩形面积都跑出来，避免漏掉某些高度的情况。

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
#define ll long long 
const int M = 100010;
ll num[M];
int main() {
	int n;
	ll weight, height;
	while (scanf("%d", &n)) {
		if (n == 0) break;
		for (int i = 1; i <= n; ++i) scanf("%lld", &num[i]);
		stack<ll> sta;
		ll ans = 0;
		num[n + 1] = 0;
		for (int i = 1; i <= n + 1; ++i) {
			while (!sta.empty() && num[i] <= num[sta.top()]) {
				height = num[sta.top()]; sta.pop(); 
				if (sta.empty()) weight = i - 1;
				else weight = i - 1 - sta.top();			
				ans = max(ans, weight * height);
			}
			sta.push(i);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

D?Max Sum of Max-K-sub-sequence (HDU - 3415)

(前缀和 + 单调队列)
题目链接

题意：给定长度为n的循环序列，计算最大长度不超过 k 的子序列的最大和
本题可以维护单调上升的队列，队列元素为到点 i 的前缀和，子段和大小为 sum[i] - sum[que[l] - 1]，如果后面进来的子段和比队尾的小，那么后面的点与前面的点相连而成的子段，一定不会取到队尾的点，那么就可以将队尾弹出。
最后只需要在每段子段和大于ans 时进行ans 和 ansr ansl 的改变就可以了

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int M = 100010;
const int INF = 0x3f3f3f3f;
int num[M << 1], sum[M << 1], que[M << 1];
void find_(int n, int k) {
	memset(que, 0, sizeof(que));
	int l = 1, r = 0;
	int ans = -INF, ansr, ansl;
	for (int i = 1; i <= 2 * n; ++i) {
		while (l <= r && i - que[l] + 1 > k) l++;
		while (l <= r && sum[i - 1] < sum[que[r] - 1]) r--;
		que[++r] = i;
		if (ans < sum[i] - sum[que[l] - 1]) {
			ans = sum[i] - sum[que[l] - 1];
			ansr = i;
			ansl = que[l];
		}
	}
	if (ansr > n) ansr -= n;
	printf("%d %d %d\n", ans, ansl, ansr);
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, k;
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &num[i]);
			num[i + n] = num[i];
		}
		for (int i = 1; i <= 2 * n; ++i) sum[i] = sum[i - 1] + num[i];
		find_(n, k);
	}
	return 0;
}