Dùng để lấy min, max trong các phần tử đã duyệt
Ví dụ: stack min:
Cấu trúc:
mảng q lưu lại các giá trị,
mảng p lưu chỉ số tương ứng,
biến d, c: đoạn q[d..c] là các giá trị cần sử dụng
Ta có: q[d] là giá trị nhỏ nhất cần tìm
Quy tắc bỏ vào và lấy ra:
Duyệt đến phần tử x:
Xét từ phải qua trái: lấy ra ngoài tất cả các phần tử lớn hơn hoặc bằng x
Lưu lại x và chỉ số tương ứng vào vị trí bên phải cùng của stack
Code:
While (d<=c)and(q[c]>=x) do dec(c);
Q[c]:=x; p[c]:=I;
Note: để tìm min trong 1 đoạn có độ dài k kết thúc tại i (đang xét):
Nếu i-p[d] > k thì tăng d
Không có nhận xét nào:
Đăng nhận xét