Stack, Queue, Deque Techniques - Preparation to IOI Part 3
Stack, Queue, Deque Techniques
Stack, Queue, Deque Techniques
Introduction
We already know the basic operations of a stack, queue, and deque from the earlier STL lecture. In this lecture, we will not repeat how push, pop, front, or top work. Instead, we will learn how these simple containers become linear-time problem-solving techniques.
Many array problems ask us to find a useful earlier element:
the nearest earlier element with a smaller value;
the first suitable element that is still inside a sliding window;
the largest value among the last k elements.
A direct solution repeatedly searches through old elements. The faster approach keeps only the elements that may still become an answer. Elements that are irrelevant, expired, or dominated are removed permanently.
We will study this idea through three related techniques:
a monotonic stack for finding the previous smaller element;
a queue of relevant indices for finding the first negative value in every window;
a monotonic deque for finding the maximum in every window.
The third technique combines the first two ideas. It removes expired candidates from the front like a queue and dominated candidates from the back like a monotonic stack.
Problem or motivation
We will use the same array for all three tasks:
a=[4,−2,3,−4,5,2,6]
and use windows of length k=3.
In general, we assume
1≤k≤n
Task 1: previous smaller element
For every position i, find the nearest position j<i such that a[j]<a[i]. Output 0 if no such position exists.
For our example, the answer is
[0,0,2,0,4,4,6]
For example, the previous smaller position for i=6 is 4, because a[4]=−4<2, while position 5 is not smaller.
Task 2: first negative value in every window
For every consecutive segment of length k, output its first negative value. Output 0 if the window contains no negative value.
The windows give
[−2,−2,−4,−4,0]
Task 3: maximum in every window
For every consecutive segment of length k, output its maximum value.
The answer is
[4,3,5,5,6]
These tasks look different, but all of them scan the array from left to right and maintain a small collection of useful earlier indices.
Naive approach
For the previous smaller element, we can start at i−1 and move left until we find a smaller value. In the worst case, we inspect almost the entire prefix for every position, so the total time is O(n2).
For either window problem, we can inspect all k values whenever a new window is formed. There are n−k+1 windows, so this takes O(nk) time. When k is close to n, this is also O(n2).
The repeated work is the problem. Consecutive windows overlap heavily, and searches for nearby positions inspect many of the same elements again. We need to remember useful candidates between steps instead of rebuilding the answer from the beginning.
Core concept
While scanning the array, we maintain a candidate container. An index stays in the container only while it can still answer the current query or some future query.
There are three main reasons to exclude or remove an index:
Irrelevant: it does not satisfy the required property. For example, a non-negative value can never be the first negative value of a window.
Expired: it is no longer inside the current window.
Dominated: a newer element is at least as useful and will remain available for longer.
The required removals determine the data structure:
What we need to access or remove
Suitable structure
The most recent surviving candidate
Stack
The earliest relevant candidate
Queue
The oldest candidate from the front and dominated candidates from the back
Deque
We usually store indices, not only values. An index tells us both the value a[i] and whether the element still belongs to the current window. It also distinguishes equal values at different positions.
Why repeated popping is still linear
The algorithms contain while loops that may remove several elements during one iteration. This can look quadratic, but an index can be removed only after it was inserted.
Each index is:
inserted into a container at most once;
removed from that container at most once.
Across the complete scan, there are at most n insertions and n removals. The total work of all inner while loops is therefore O(n). This is called an amortized analysis: one iteration may be expensive, but all iterations together are linear.
Main algorithm
Monotonic stack: previous smaller element
The stack stores indices whose values are strictly increasing from bottom to top.
Before answering position i, we remove every top index j with a[j]≥a[i]. Such an index cannot be the previous strictly smaller element for i.
Removing it permanently is also safe. The current index i is newer and has a value no greater than a[j]. For any future position where j could be a smaller candidate, i would also be a smaller candidate and would be closer.
After these removals:
if the stack is empty, there is no previous smaller position;
otherwise, the top is the nearest previous smaller position.
We then push i for future positions.
Queue of relevant indices: first negative value
The queue stores only indices whose values are negative. These indices appear in increasing order because we process the array from left to right.
When position i enters:
if a[i]<0, push i into the queue;
once a complete window [l,i] exists, remove indices smaller than l from the front;
the front is now the earliest negative index in the window.
We do not need to store non-negative elements at all. They can never become an answer to this task.
Monotonic deque: maximum in every window
For a window maximum, we need two different kinds of removal:
an old index may expire from the left side of the window;
a small value may become dominated by a newer, larger value.
A deque supports both operations.
This technique is also commonly called a monotonic queue, although we implement it with deque because we must remove elements from both ends.
The deque maintains two invariants:
its indices increase from front to back;
their values strictly decrease from front to back.
For every position i:
remove expired indices from the front;
while the value at the back is at most a[i], remove that index from the back;
push i at the back;
when a complete window exists, its maximum is at the front.
When two values are equal, we keep the newer one. It gives the same maximum but expires later, so the older equal value is dominated.
The implementation contains five functions:
get_previous_smaller applies the monotonic-stack technique.
get_first_negative applies the filtered-queue technique.
get_window_maximum applies the monotonic-deque technique.
print outputs one 1-indexed answer array.
The main function reads the input, calls the three algorithms, and prints their results.
Algorithm:
Each algorithm processes every index a constant number of times. The previous O(n2) and O(nk) approaches become O(n).
Implementation
Complexity
For each of the three algorithms:
Time:O(n)
Auxiliary memory:O(n)
1. Function get_previous_smaller(a, n):
1.1. Create an empty stack st.
1.2. For i from 1 to n:
1.2.1. While st is not empty and a[st.top] >= a[i]:
1.2.1.1. Remove st.top.
1.2.2. If st is empty, set answer[i] = 0.
1.2.3. Otherwise, set answer[i] = st.top.
1.2.4. Push i into st.
1.3. Return answer.
2. Function get_first_negative(a, n, k):
2.1. Create an empty queue q.
2.2. For i from 1 to n:
2.2.1. If a[i] < 0, push i into q.
2.2.2. If i >= k:
2.2.2.1. Set l = i - k + 1.
2.2.2.2. While q is not empty and q.front < l:
2.2.2.2.1. Remove q.front.
2.2.2.3. If q is empty, set answer[l] = 0.
2.2.2.4. Otherwise, set answer[l] = a[q.front].
2.3. Return answer.
3. Function get_window_maximum(a, n, k):
3.1. Create an empty deque dq.
3.2. For i from 1 to n:
3.2.1. Set l = i - k + 1.
3.2.2. While dq is not empty and dq.front < l:
3.2.2.1. Remove dq.front.
3.2.3. While dq is not empty and a[dq.back] <= a[i]:
3.2.3.1. Remove dq.back.
3.2.4. Push i at the back of dq.
3.2.5. If i >= k, set answer[l] = a[dq.front].
3.3. Return answer.
4. Function print(a, n):
4.1. Output a[1], a[2], ..., a[n].
5. Function main():
5.1. Read n, k, and a[1..n].
5.2. Call get_previous_smaller.
5.3. Call get_first_negative.
5.4. Call get_window_maximum.
5.5. Print the three answer arrays.
#include <bits/stdc++.h>using namespace std;vector<int> get_previous_smaller(const vector<int> &a, int n){ stack<int> st; vector<int> answer(n + 1); for(int i = 1; i <= n; i++){ while(!st.empty() && a[st.top()]>= a[i]){ st.pop();} if(st.empty()){ answer[i] = 0;} else{ answer[i] = st.top();} st.push(i);} return answer;}vector<int> get_first_negative(const vector<int> &a, int n, int k){ queue<int> q; vector<int> answer(n - k + 2); for(int i = 1; i <= n; i++){ if(a[i]< 0){ q.push(i);} if(i >= k){ int l = i - k + 1; while(!q.empty() && q.front()< l){ q.pop();} if(q.empty()){ answer[l] = 0;} else{ answer[l] = a[q.front()];}}} return answer;}vector<int> get_window_maximum(const vector<int> &a, int n, int k){ deque<int> dq; vector<int> answer(n - k + 2); for(int i = 1; i <= n; i++){ int l = i - k + 1; while(!dq.empty() && dq.front()< l){ dq.pop_front();} while(!dq.empty() && a[dq.back()]<= a[i]){ dq.pop_back();} dq.push_back(i); if(i >= k){ answer[l] = a[dq.front()];}} return answer;}void print(const vector<int> &a, int n){ for(int i = 1; i <= n; i++){ cout << a[i]; if(i < n){ cout << ' ';}} cout << endl;}int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<int> a(n + 1); for(int i = 1; i <= n; i++){ cin >> a[i];} vector<int> previous_smaller = get_previous_smaller(a, n); vector<int> first_negative = get_first_negative(a, n, k); vector<int> window_maximum = get_window_maximum(a, n, k); print(previous_smaller, n); print(first_negative, n - k + 1); print(window_maximum, n - k + 1); return 0;}