Mục lục:
I. Khái niệm
II. Các bài sử dụng stack đơn điệu và cách cài đặt.
Phần I. Khái niệm
1. Khái niệm Stack
- Stack là một danh sách được bổ sung 2 thao tác: thêm một phần tử vào cuối danh sách, và loại bỏ một phần tử ở cuối danh sách. Ví trí cuối của Stack được gọi là đỉnh (top). - Nguyên lý của stack là LIFO (Last In, First Out - vào sau ra trước).
- Trong thư viện chuẩn C++ các thao tác thường được sử dụng tron stack là :
+ push : thêm phần tử vào cuối danh sách.
+ top : trả về giá trị phần tử ở cuối danh sách.
+ pop : loại bỏ phần tử ở cuối danh sách.
+ empty : trả về trạng thái của stack (true nếu stack rỗng, false nếu stack có ít nhất 1 phần tử)
+ size : trả về số phần tử hiện có trong stack.
2. Stack đơn điệu
- Stack đơn điệu là ngăn xếp mà các phần tử của nó xét từ đáy của Stack đến đỉnh Stack tạo thành một dãy số đơn điệu.
Giả sử: 1, 2, 5, 7, 10;
Phần II. Các bài sử dụng stack đơn điệu và cách cài đặt.
Bài 1: NEAREST : Cho mảng a gồm N phần tử. Với mỗi pần tử ở vị trí i (1 <= i <= N) cần chỉ ra số đứng trước nó gần nhất và số đứng sau nó gần nhất mà có giá trị lớn hơn số đó. Nếu không tồn tại ghi ra 0. (1 <= N, a[i] <= 1e6)
*Nhận xét: để giải quyết bài toán này ta cần làm được bài toán đơn giản hơn: với mỗi i ta chỉ cần tìm j thỏa mãn điều kiện gốc, mà j < i. Để duyệt được thì ta sẽ có ý tưởng như sau:
Ban đầu, tạo ra 1 danh sách xếp hàng để xếp các số vào trong đó.
Với số i chạy từ 1 đến n, ta xét:
- Xóa tất cả các phần tử đang ở trong danh sách mà bé hơn hoặc bằng a[i] nếu như có một phần tử j trong danh sách mà a[j] > a[i] thì những số phải xóa sẽ nằm trong khoảng từ phần tử j + 1 đến phần tử cuối danh sách.
+ Nếu danh sách khi này rỗng thì tức là trước a[i] không có số nào lớn hơn nó => in ra 0
+ Nếu danh sách không rỗng thì số gần nhất đứng trước mà lớn hơn a[i] chính là số ở cuối danh sách => in ra số đó.
- Cho số i vào sanh sách và xét tiếp tục
Với cách sắp xếp như thế này thì mỗi khi xét xong danh sách sẽ trở thành một dãy đơn điệu.
Với cách xét này ta sẽ sử dụng stack.
Để xóa các phần tử bé hơn a[i] trong danh sách ta sẽ sử dụng lệnh pop
Để kiểm tra danh sách rỗng ta sử dụng lệnh empty
Để lấy số đứng cuối danh sách ta sẽ sử dụng lệnh top
Để thêm số i vào danh sách ta sẽ sử dụng lệnh push
Code minh họa C++ bài toán nhỏ:
stack < int > s;
for (int i = 1; i <= n; i ++)
{
while (!s.empty() && a[i] >= a[s.top()])
s.pop();
ans[i] = 0;
if (!s.empty())
ans[i] = s.top();
s.push(i);
}
Code minh họa C++ bài NEAREST:
#include < bits/stdc++.h >
#define PB push_back
#define pii pair
#define vi vector
#define F first
#define S second
#define reset(x) memset(x,0,sizeof(x))
#define sz(x) int(x.size())
#define Task "NEAREST"
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
int a[10000005];
pii ans[1000005];
stack < int > s;
void tinh()
{
for (int i = 1; i <= n; i ++)
{
while (!s.empty() && a[i] >= a[s.top()])
s.pop();
ans[i].F = 0;
if (!s.empty())
ans[i].F = s.top();
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = n; i >= 1; i --)
{
while (!s.empty() && a[i] >= a[s.top()])
s.pop();
ans[i].S = 0;
if (!s.empty())
ans[i].S = s.top();
s.push(i);
}
for (int i = 1; i <= n; i ++)
cout << ans[i].F << " " << ans[i].S << "\n";
}
void nhap() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
}
int main() {
nhap();
tinh();
}
Bài 2 : COST: Cho dãy số nguyên a[1], a[2], . . ., a[n] (0 ≤ a[i] ≤ 1e9 , 1 ≤ n ≤ 1e6 ). Với dãy số nguyên này ta có thể thực hiện phép xử lý Reduce(i) thay thế 2 phần tử a[i] và a[i+1] bằng max{a[i], a[i+1]} với chi phí là max{a[i], a[i+1]}. Sau n-1 lần thực hiện phép xử lý trên, ta được dãy số độ dài 1. Chi phí biến đổi dãy được tính bằng tổng chi phí của tất cả các phép xử lý đã thực hiện.
Cho n và các số a[i]. Hãy xác định chi phí nhỏ nhất đưa dãy về độ dài bằng 1.
Mời các bạn cho ý tưởng và (hoặc) code minh họa cho bài COST. Code chuẩn sử dụng stack đơn điệu sẽ được up vào bài viết về stack đơn điệu tiếp theo!
Bài viết được tham khảo từ VNOI.