Ngăn xếp & Hàng đợi đơn điệu
Ngăn xếp đơn điệu
Giới thiệu
Ngăn xếp đơn điệu là một cấu trúc dữ liệu có tính chất đơn điệu, tức là các phần tử trong ngăn xếp được sắp xếp theo thứ tự tăng dần hoặc giảm dần. Khác với hàng đợi đơn điệu, ngăn xếp chỉ cho phép thao tác ở một đầu.
Quy trình
Thêm phần tử
Khi thêm một phần tử vào ngăn xếp đơn điệu, để duy trì tính chất đơn điệu của ngăn xếp, cần loại bỏ các phần tử không cần thiết từ đỉnh ngăn xếp sao cho phần tử mới được đưa vào vẫn giữ được tính chất đơn điệu và số lượng phần tử bị loại bỏ là ít nhất.
Mã giả
thêm x
khi !ngan_xep.rỗng() và ngan_xep.top() < x
ngan_xep.pop()
ngan_xep.push(x)
Ví dụ áp dụng
Cài đặt mã nguồn
#include<bits/stdc++.h>
using namespace std;
int n,a[3000005],b[3000005];
stack <int> s;
int main()
{
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=n;i>=1;i--)
{
while(!s.empty() && a[s.top()] <= a[i])
{
s.pop();
}
if(!s.empty())
{
b[i] = s.top();
}
else
{
b[i] = 0;
}
s.push(i);
}
for(int i = 1;i <= n;i++)
{
cout << b[i] << " ";
}
return 0;
}
Định nghĩa được lấy trực tiếp từ OI Wiki
Hàng đợi đơn điệu
Giới thiệu
Trước tiên, hãy cùng xem xét một bài toán kinh điển: cửa sổ trượt (sliding window)
Cách tiếp cận đơn giản nhất là với mỗi đoạn từ i đến i+k-1, ta sẽ so sánh từng phần tử để tìm giá trị lớn nhất (hoặc nhỏ nhất). Độ phức tạp thời gian là khoảng O(n * k).
Rõ ràng, cách này lặp lại rất nhiều công việc. Ngoài ra k-1 phần tử đầu và cuối, mọi phần tử đều được so sánh k lần. Với dữ liệu n <= 1000000, nếu k lớn thì sẽ bị quá thời gian.
Lúc này, chúng ta sử dụng hàng đợi đơn điệu.
Định nghĩa
Tên gọi đã nói lên tất cả: "đơn điệu" và "hàng đợi".
- Đơn điệu: các phần tử trong hàng đợi tuân theo quy luật tăng dần hoặc giảm dần.
- Hàng đợi: chỉ có thể thêm/xóa phần tử ở đầu và cuối hàng đợi.
Phân tích ví dụ
Đúng vậy, nó nằm ở đây
Mã nguồn
// 1. Cập nhật đầu hàng (nếu phần tử hiện tại đã quá cũ, có thể loại bỏ, head++)
// 2. Thêm vào cuối hàng (khi thêm mới, phải loại bỏ các phần tử không cần thiết từ cuối về trước)
#include<bits/stdc++.h>
using namespace std;
int n,m;
int q1[1000001],q2[1000001];
int a[1000001];
int tim_min()
{
int dau = 1, cuoi = 0;
for(int i = 1;i <= n;i++)
{
while(dau <= cuoi && q1[dau] <= i - m) dau++;
while(dau <= cuoi && a[i] < a[q1[cuoi]]) cuoi--;
q1[++cuoi] = i;
if(i >= m ) cout << a[q1[dau]] << " ";
}
cout << "\n";
return 0;
}
int tim_max()
{
int dau = 1, cuoi = 0;
for(int i = 1;i <= n;i++)
{
while(dau <= cuoi && q2[dau] <= i - m) dau++;
while(dau <= cuoi && a[i] > a[q2[cuoi]]) cuoi--;
q2[++cuoi] = i;
if(i >= m) cout << a[q2[dau]] << " ";
}
return 0;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> a[i];
tim_min();
tim_max();
return 0;
}