Monotone queue and monotone stack

Monotone queue and monotone stack

Monotonic queue

  • The classical sliding window problem: find the maximum value of all subintervals with length m (m < n) in A sequence A with length n. N < = 2E6.

Line segment trees are easy to tle. We need an o(n) algorithm to solve this problem.

Idea:

  • Consider each window, where at least one position must be the maximum.

  • If there is one, in this window, all the numbers in front of the maximum value are useless to us (not only small, but also exit early); Similarly, if there is more than one maximum value, we can select the last maximum value (the front maximum values can not only be replaced, but also exit early).

  • For all the numbers behind them, it is necessary to consider that after the maximum value exits the window, they have the "potential" to become the maximum value.

  • However, among all the numbers after this, if there is \ (A_i < = a_j\) and \ (I < j\), then this \ (A_i\) does not need to be considered (it is not only small, but also exits early).

  • Therefore, in each window, we only need to record the current maximum value and the number after the maximum value, if and only if there is no number greater than or equal to this number.

It can be seen that this window can be simulated with a two-way queue. Whenever a number is added in the rear, all numbers less than it must be eliminated from the end of the queue to ensure that there is no number greater than or equal to it behind each number in the queue within the window. When the queue head element is not in the window range, the queue head element is out of the queue. After this operation, the elements in the team are monotonic, so it is called monotonic queue

Reference topic: Luogu P1440 (slightly different)

P1440 array simulation queue code:

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

using namespace std;

int n, m; 
struct ab
{
	int l;	//position 
	int v;
} que[2000005];
int head = 1, tail = 1;
int main()
{
	scanf("%d%d", &n, &m);
	printf("0\n");
	for (int i = 1; i < n; ++i)
	{
		int num;
		scanf("%d", &num);
		while (tail != head && num <= que[tail - 1].v)
		{
			--tail;
		}
		que[tail].l = i;
		que[tail++].v = num;
		while (que[head].l <= i - m)
		{
			++head;
		}
		printf("%d\n", que[head].v);
	}
	scanf("%d", &n);	//Swallow the input of the last number 
	return 0;
}

Monotone stack

After understanding the monotone queue, the monotone stack makes people think that all elements in the stack are monotone as the name suggests

Problem solving:

  • 1. find the subscript of the first number larger / smaller than yourself after / before any number in a sequence

  • 2. find out how many smaller numbers are connected to the rear / front of any number in a sequence

The essence of these two problems is the same, but the naive algorithm is obviously \ (O(n^2) \), and we need to use monotone stack to reduce the dimension in time.

  • For example, find the subscript of the first larger number after any number in a sequence. If it does not exist, it will be 0, and the sequence length n < = 3e6.
    • At first we put an INF at the bottom of the stack
    • Stack the sequence from left to right
    • When the top of the stack element is smaller than the current number of hours, the top of the stack element leaves the stack and marks the corresponding answer of the top of the stack element as the subscript of the stack element. In this way, the top of the stack element is greater than or equal to the stack element
    • The corresponding answer of the elements left in the stack is 0

Template questions: Luogu P5788

P5788 array simulation stack code

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

using namespace std;

int n;
int top = 1;

struct ab
{
	int v;
	int l;
} sta[3000005];

int ans[3000005] = {0};

int main()
{
	scanf("%d", &n);
	int xx;
	scanf("%d", &xx);
	sta[top].l = 1;
	sta[top++].v = xx;
	for (int i = 2; i <= n; ++i)
	{
		scanf("%d", &xx);
		while (top != 1 && sta[top - 1].v < xx)
		{
			ans[sta[top - 1].l] = i;
			--top;
		}
		sta[top].l = i;
		sta[top++].v = xx;
	}
	while (top != 1)
	{
		ans[sta[top - 1].l] = 0;
		--top;
	}
	for (int i = 1; i < n; ++i)
	{
		printf("%d ", ans[i]);
	}
	printf("%d", ans[n]);
	return 0;
}

Tags: data structure

Posted by turek on Sun, 29 May 2022 23:17:32 +0530