Stack là một trong những cấu trúc dữ liệu đầu tiên mà người học lập trình thi đấu cần nắm thật chắc, nhưng giá trị của nó không chỉ nằm ở vài thao tác quen thuộc như push, pop hay top. Bản chất của Stack là nguyên tắc vào sau, ra trước (LIFO - Last In, First Out), và từ nguyên tắc rất đơn giản đó lại mở ra một loạt kỹ thuật quan trọng xuất hiện xuyên suốt Competitive Programming. Khi gặp một phần tử chưa thể xử lý ngay, ta có thể đưa nó vào Stack để “chờ”, rồi chỉ lấy nó ra khi xuất hiện thông tin mới đủ để giải quyết. Chính cách tư duy này giúp Stack xuất hiện tự nhiên trong kiểm tra ngoặc và cấu trúc lồng nhau (Nesting), phân tích biểu thức (Expression Parsing), mô phỏng lịch sử thao tác, thay đệ quy bằng Stack, xây Min Stack, Max Stack, xử lý Stack đơn điệu (Monotonic Stack), tìm phần tử lớn hơn hoặc nhỏ hơn gần nhất, giải Histogram, đếm đóng góp của phần tử trên các đoạn con (Contribution Counting), xây cây Cartesian (Cartesian Tree), kết hợp với Quy hoạch động (Dynamic Programming - DP), Tham lam (Greedy), DFS không đệ quy (Iterative DFS), thuật toán Hierholzer cho đường đi Euler, cho tới những kỹ thuật nâng cao như Stack bền vững (Persistent Stack), Rollback và xử lý Offline. Điều quan trọng nhất khi học Stack không phải là thuộc lòng một mẫu code, mà là nhìn ra được câu hỏi: “Những phần tử nào đã xuất hiện nhưng vẫn chưa được giải quyết?” Nếu xác định đúng nhóm phần tử đó và hiểu rõ điều kiện khi nào chúng phải vào Stack, khi nào chúng phải rời Stack, ta sẽ thấy rất nhiều bài tưởng như phức tạp thực ra chỉ là những biến thể khác nhau của cùng một ý tưởng. Vì vậy, lộ trình này được xây theo từng giai đoạn từ nền tảng LIFO đến các kỹ thuật Stack nâng cao, giúp người học không chỉ biết dùng Stack mà còn hình thành phản xạ nhận dạng đúng bản chất bài toán và lựa chọn Stack đúng lúc.

Đăng nhập để tham gia lộ trình luyện tập

LỘ TRÌNH STACK

Stack là cấu trúc dữ liệu hoạt động theo nguyên tắc vào sau, ra trước (LIFO - Last In, First Out).

Nếu lần lượt đưa vào:

a_1,a_2,\ldots,a_n

thì khi lấy ra sẽ theo thứ tự:

a_n,a_{n-1},\ldots,a_1

Các thao tác cơ bản như đưa phần tử vào (push), lấy phần tử ở đỉnh (pop) và xem phần tử ở đỉnh (top) thường có độ phức tạp:

O(1)

Điểm quan trọng nhất khi học Stack là hiểu: phần tử còn nằm trong Stack thường là phần tử chưa được xử lý xong.

Giai đoạn 1 - Stack cơ bản, LIFO và giảm chuỗi

Stack phù hợp với những bài mà phần tử xuất hiện sau cần được xử lý trước.

Ví dụ điển hình là xóa các cặp phần tử kề nhau. Ta duyệt từ trái sang phải, dùng Stack để giữ những phần tử chưa bị loại.

tạo Stack rỗng

với mỗi phần tử x:

    nếu Stack chưa rỗng
    và x có thể ghép hoặc triệt tiêu với phần tử ở đỉnh:

        xóa phần tử ở đỉnh

    ngược lại:

        đưa x vào Stack

Nếu mỗi phần tử chỉ vào Stack một lần và ra khỏi Stack nhiều nhất một lần thì tổng thời gian là:

O(n)

Cách phân tích này gọi là phân tích khấu hao (Amortized Analysis).

Giai đoạn 2 - Ngoặc và cấu trúc lồng nhau (Nesting)

Ngoặc một loại

Với chuỗi chỉ có ( và ), có thể dùng biến cân bằng (balance).

Gặp (:

balance=balance+1

Gặp ):

balance=balance-1

Chuỗi hợp lệ khi:

balance\ge0

ở mọi thời điểm và cuối cùng:

balance=0

balance = 0

duyệt từng ký tự c:

    nếu c là '(':
        tăng balance lên 1

    nếu c là ')':
        giảm balance đi 1

    nếu balance < 0:
        kết luận không hợp lệ

sau khi duyệt xong:

    nếu balance = 0:
        hợp lệ
    ngược lại:
        không hợp lệ

Nhiều loại ngoặc

Khi có (), [], {}, ta cần Stack để nhớ loại ngoặc mở gần nhất.

tạo Stack rỗng

duyệt từng ký tự c:

    nếu c là ngoặc mở:
        đưa c vào Stack

    nếu c là ngoặc đóng:

        nếu Stack rỗng:
            không hợp lệ

        nếu ngoặc ở đỉnh không khớp với c:
            không hợp lệ

        xóa ngoặc ở đỉnh

sau khi duyệt xong:

    nếu Stack rỗng:
        hợp lệ
    ngược lại:
        không hợp lệ

Với bài phức tạp hơn, mỗi phần tử trong Stack có thể là một khung trạng thái (Stack Frame), lưu thêm vị trí, tổng, số lượng hoặc trạng thái xử lý.

Giai đoạn 3 - Biểu thức và phân tích cú pháp (Expression Parsing)

Biểu thức hậu tố (Postfix)

Với toán tử nhị phân, phải lấy toán hạng phải trước rồi mới lấy toán hạng trái.

right=pop()

left=pop()

result=left\ op\ right

tạo Stack số rỗng

duyệt từng token:

    nếu token là số:
        đưa số vào Stack

    nếu token là toán tử:

        lấy toán hạng phải
        lấy toán hạng trái

        tính kết quả

        đưa kết quả trở lại Stack

kết quả cuối là phần tử còn lại trong Stack

Độ ưu tiên toán tử (Precedence)

Ví dụ:

p(+)=p(-)=1

p(*)=p(/)=2

Khi chuyển từ biểu thức trung tố (Infix) sang hậu tố (Postfix), Stack dùng để giữ các toán tử chưa được xuất ra.

tạo Stack toán tử rỗng
tạo dãy kết quả rỗng

duyệt từng token x:

    nếu x là số hoặc biến:
        đưa x vào kết quả

    nếu x là '(':
        đưa x vào Stack

    nếu x là ')':

        lấy các toán tử khỏi Stack
        và đưa vào kết quả
        cho đến khi gặp '('

        bỏ '('

    nếu x là toán tử:

        trong khi toán tử ở đỉnh
        cần được xử lý trước x:

            đưa toán tử ở đỉnh vào kết quả
            xóa toán tử đó khỏi Stack

        đưa x vào Stack

sau khi duyệt xong:

    đưa các toán tử còn lại vào kết quả

Quy tắc trên chính là ý tưởng của thuật toán Shunting-yard.

Với số nhiều chữ số:

value_{mới}=10\cdot value_{cũ}+digit

value = 0

trong khi ký tự hiện tại là chữ số:

    value = value * 10 + chữ_số_hiện_tại

Giai đoạn 4 - Hai Stack và thay đệ quy bằng Stack

Hàng đợi bằng hai Stack (Queue using Two Stacks)

Một Stack dùng để nhận phần tử mới, Stack còn lại dùng để lấy phần tử cũ nhất.

khi thêm x:

    đưa x vào Stack vào

khi cần lấy phần tử đầu:

    nếu Stack ra rỗng:

        chuyển toàn bộ phần tử
        từ Stack vào sang Stack ra

    lấy phần tử ở đỉnh Stack ra

Mỗi phần tử chỉ bị chuyển một số lần cố định nên chi phí trung bình mỗi thao tác là:

O(1)

theo phân tích khấu hao (Amortized Analysis).

Trình soạn thảo bằng hai Stack

Một Stack lưu phần bên trái con trỏ, Stack còn lại lưu phần bên phải.

di chuyển con trỏ sang trái:

    nếu Stack trái chưa rỗng:
        lấy phần tử ở đỉnh Stack trái
        đưa sang Stack phải

di chuyển con trỏ sang phải:

    nếu Stack phải chưa rỗng:
        lấy phần tử ở đỉnh Stack phải
        đưa sang Stack trái

Thay đệ quy bằng Stack (Recursion-to-Stack)

Mỗi lần gọi hàm đệ quy có thể xem như một khung gọi hàm (Call Frame).

đưa trạng thái ban đầu vào Stack

trong khi Stack chưa rỗng:

    xét trạng thái ở đỉnh

    nếu còn nhánh chưa xử lý:

        chọn nhánh tiếp theo

        lưu lại vị trí đang xử lý

        đưa trạng thái con vào Stack

    ngược lại:

        xử lý công việc khi kết thúc trạng thái

        xóa trạng thái ở đỉnh

Giai đoạn 5 - Min Stack, Max Stack và Stack có giá trị tổng hợp

Min Stack

Mỗi phần tử lưu thêm giá trị nhỏ nhất từ đáy Stack đến vị trí đó.

Khi thêm $x$ :

$$min_{mới}= \begin{cases} x,&\text{nếu Stack rỗng}\\ \min(x,min_{cũ}),&\text{ngược lại} \end{cases}$$

khi thêm x:

    nếu Stack rỗng:
        min_moi = x
    ngược lại:
        min_moi = min(x, min ở đỉnh)

    đưa cặp (x, min_moi) vào Stack

Giá trị nhỏ nhất hiện tại chính là giá trị min ở đỉnh Stack.

Truy vấn này có độ phức tạp:

O(1)

Max Stack

Làm tương tự:

max_{mới}=\max(x,max_{cũ})

Stack tổng hợp (Aggregate Stack)

Ý tưởng tổng quát là mỗi phần tử lưu:

(value,\ aggregate)

trong đó:

aggregate_{mới} = combine(aggregate_{cũ},value)

combine có thể là min, max hoặc một phép kết hợp phù hợp khác.

Giai đoạn 6 - Stack đơn điệu (Monotonic Stack)

Stack đơn điệu là Stack được giữ theo thứ tự tăng hoặc giảm.

Nó thường được dùng để tìm phần tử lớn hơn hoặc nhỏ hơn gần nhất.

Phần tử nhỏ hơn gần nhất bên trái (Previous Smaller)

Muốn tìm vị trí gần nhất bên trái có giá trị nhỏ hơn $a_i$ :

tạo Stack chỉ số rỗng

duyệt i từ trái sang phải:

    trong khi Stack chưa rỗng
    và giá trị ở đỉnh >= a[i]:

        xóa đỉnh

    nếu Stack chưa rỗng:
        đỉnh Stack là vị trí cần tìm

    đưa i vào Stack

Nếu cần nhỏ hơn hoặc bằng thì điều kiện xóa đổi thành:

trong khi Stack chưa rỗng
và giá trị ở đỉnh > a[i]:

    xóa đỉnh

Phần tử nhỏ hơn gần nhất bên phải (Next Smaller)

tạo Stack chỉ số rỗng

duyệt i từ trái sang phải:

    trong khi Stack chưa rỗng
    và a[i] < giá trị ở đỉnh:

        vị trí ở đỉnh có phần tử nhỏ hơn gần nhất bên phải là i

        xóa đỉnh

    đưa i vào Stack

Phần tử lớn hơn gần nhất bên phải (Next Greater)

tạo Stack chỉ số rỗng

duyệt i từ trái sang phải:

    trong khi Stack chưa rỗng
    và a[i] > giá trị ở đỉnh:

        vị trí ở đỉnh có phần tử lớn hơn gần nhất bên phải là i

        xóa đỉnh

    đưa i vào Stack

Mỗi phần tử vào Stack một lần và ra khỏi Stack nhiều nhất một lần nên tổng thời gian là:

O(n)

Với các phần tử bằng nhau (duplicate), cần đặc biệt chú ý sự khác nhau giữa > và >=, hoặc giữa < và <=.

Giai đoạn 7 - Histogram và hình chữ nhật lớn nhất

Cho dãy chiều cao:

h_1,h_2,\ldots,h_n

Với cột $i$ , gọi:

$L_i$ là vị trí gần nhất bên trái thấp hơn $h_i$ .
$R_i$ là vị trí gần nhất bên phải thấp hơn $h_i$ .

Chiều rộng lớn nhất mà $h_i$ làm chiều cao nhỏ nhất là:

W_i=R_i-L_i-1

Diện tích:

A_i=h_iW_i

Bài toán này thường được gọi là hình chữ nhật lớn nhất trong Histogram (Largest Rectangle in Histogram).

thêm một cột chiều cao 0 ở cuối
tạo Stack chỉ số rỗng

duyệt từng vị trí i:

    trong khi Stack chưa rỗng
    và chiều cao ở đỉnh > chiều cao hiện tại:

        j = vị trí ở đỉnh
        xóa j khỏi Stack

        nếu Stack rỗng:
            chiều_rộng = i
        ngược lại:
            chiều_rộng = i - vị_trí_đỉnh_mới - 1

        diện_tích = h[j] * chiều_rộng

        cập nhật đáp án

    đưa i vào Stack

Cột chiều cao $0$ ở cuối được gọi là phần tử chặn (Sentinel), giúp xử lý hết các cột còn lại trong Stack.

Từ ma trận về Histogram

Với ma trận nhị phân:

khởi tạo height[j] = 0

duyệt từng hàng:

    với mỗi cột j:

        nếu ô hiện tại là 1:
            tăng height[j] lên 1
        ngược lại:
            height[j] = 0

    giải bài Histogram trên mảng height

Nếu ma trận có $n$ hàng và $m$ cột:

O(nm)

Giai đoạn 8 - Đếm đóng góp (Contribution Counting)

Thay vì duyệt từng đoạn con, ta xét xem một phần tử đóng góp cho bao nhiêu đoạn.

Với $a_i$ , gọi:

$P_i$ là biên bên trái.
$N_i$ là biên bên phải.

Số cách chọn đầu trái:

left=i-P_i

Số cách chọn đầu phải:

right=N_i-i

Số đoạn mà $a_i$ đại diện:

left\cdot right

Đóng góp:

a_i\cdot left\cdot right

Tổng giá trị nhỏ nhất của mọi đoạn con (Sum of Subarray Minimums)

SumMin= \sum_i a_i(i-P_i)(N_i-i)

tìm biên trái P[i]
tìm biên phải N[i]

answer = 0

với mỗi i:

    left = i - P[i]
    right = N[i] - i

    contribution = a[i] * left * right

    cộng contribution vào answer

Để không đếm trùng khi có phần tử bằng nhau, một phía nên dùng điều kiện nghiêm ngặt (strict) và phía còn lại cho phép bằng nhau (non-strict).

Ví dụ:

$$P_i=\text{phần tử nhỏ hơn thật sự gần nhất bên trái}$$$$N_i=\text{phần tử nhỏ hơn hoặc bằng gần nhất bên phải}$$

Tổng giá trị lớn nhất của mọi đoạn con (Sum of Subarray Maximums)

Làm tương tự với các biên lớn hơn.

Nếu cần tổng:

\max-\min

trên mọi đoạn thì:

Ans=SumMax-SumMin

Giai đoạn 9 - Cây Cartesian (Cartesian Tree)

Cây Cartesian là cây nhị phân vừa giữ thứ tự của mảng khi duyệt giữa (inorder), vừa thỏa tính chất heap.

Với Min Cartesian Tree:

a_{parent}\le a_{child}

Có thể xây cây trong thời gian tuyến tính bằng Stack đơn điệu.

tạo Stack chỉ số rỗng

duyệt i từ trái sang phải:

    last = không có

    trong khi Stack chưa rỗng
    và giá trị ở đỉnh > a[i]:

        last = đỉnh Stack
        xóa đỉnh

    nếu Stack chưa rỗng:
        i trở thành con phải của đỉnh hiện tại

    nếu last tồn tại:
        last trở thành con trái của i

    đưa i vào Stack

Độ phức tạp:

O(n)

Một liên hệ quan trọng với truy vấn nhỏ nhất trên đoạn (RMQ - Range Minimum Query):

RMQ(l,r)=LCA(l,r)

trên Min Cartesian Tree tương ứng, trong đó LCA là tổ tiên chung thấp nhất (Lowest Common Ancestor).

Giai đoạn 10 - Stack kết hợp Quy hoạch động (DP) và Tham lam (Greedy)

Ở các bài nâng cao, Stack thường chỉ giúp tìm nhanh vị trí hoặc trạng thái quan trọng trước đó.

Stack kết hợp Quy hoạch động (Dynamic Programming)

Giả sử Stack giúp tìm được vị trí $p_i$ .

Ta có thể gặp dạng chuyển:

dp[i]=dp[p_i]+cost(p_i+1,i)

duyệt i từ trái sang phải:

    trong khi Stack chưa rỗng
    và trạng thái ở đỉnh không còn hữu ích:

        xóa đỉnh

    nếu Stack chưa rỗng:
        p[i] = đỉnh Stack

    tính dp[i] từ p[i]

    đưa i vào Stack

Stack tham lam (Greedy Monotonic Stack)

Một dạng phổ biến là xây dãy nhỏ nhất hoặc lớn nhất theo thứ tự từ điển.

duyệt từng phần tử x:

    trong khi Stack chưa rỗng
    và phần tử ở đỉnh tệ hơn x
    và vẫn còn quyền loại:

        xóa đỉnh
        giảm số lần được loại

    đưa x vào Stack

Nếu mỗi giá trị chỉ được xuất hiện một lần, chỉ được xóa phần tử ở đỉnh khi nó còn xuất hiện phía sau.

Vị trí xuất hiện cuối (Last Occurrence) thường được lưu bằng:

last[x]

Điều kiện:

last[x]>i

duyệt vị trí i:

    x = phần tử hiện tại

    nếu x đã được chọn:
        bỏ qua

    trong khi Stack chưa rỗng
    và đỉnh lớn hơn x
    và đỉnh còn xuất hiện phía sau:

        đánh dấu đỉnh là chưa được chọn
        xóa đỉnh

    đưa x vào Stack
    đánh dấu x đã được chọn

Giai đoạn 11 - Stack trong DFS và đồ thị

DFS không đệ quy (Iterative DFS)

tạo Stack rỗng
đưa đỉnh bắt đầu vào Stack

trong khi Stack chưa rỗng:

    lấy đỉnh u khỏi Stack

    nếu u đã thăm:
        bỏ qua

    đánh dấu u đã thăm

    với mỗi đỉnh kề v của u:

        nếu v chưa thăm:
            đưa v vào Stack

Độ phức tạp:

O(n+m)

DFS cần biết thời điểm đi vào và đi ra

Với các thuật toán như thành phần liên thông mạnh (SCC - Strongly Connected Components), cầu (Bridge), đỉnh khớp (Articulation Point) hoặc giá trị low-link, chỉ lưu đỉnh là chưa đủ.

Mỗi trạng thái nên nhớ:

(u,\ cha,\ cạnh\ tiếp\ theo)

đưa trạng thái của đỉnh bắt đầu vào Stack

trong khi Stack chưa rỗng:

    xét trạng thái ở đỉnh

    nếu còn cạnh chưa duyệt:

        lấy cạnh tiếp theo

        ghi nhớ vị trí cạnh tiếp theo

        nếu đi được sang đỉnh con:

            xử lý lúc đi vào đỉnh con

            đưa trạng thái của đỉnh con vào Stack

    ngược lại:

        xử lý lúc rời đỉnh hiện tại

        xóa trạng thái ở đỉnh

Low-link

Khi đi vào $u$ :

low[u]=tin[u]

Sau khi xử lý xong đỉnh con $v$ :

low[u]=\min(low[u],low[v])

Với cạnh ngược (Back Edge) tới $v$ :

low[u]=\min(low[u],tin[v])

khi đi vào u:

    tin[u] = low[u] = thời_gian_hiện_tại
    tăng thời_gian

sau khi xử lý xong con v:

    low[u] = min(low[u], low[v])

nếu gặp cạnh ngược tới v:

    low[u] = min(low[u], tin[v])

Giai đoạn 12 - Đường đi Euler và Hierholzer

Thuật toán Hierholzer dùng Stack để giữ đường đi hiện tại (Current Trail).

Khi đỉnh hiện tại còn cạnh chưa dùng, ta tiếp tục đi.

Khi không còn cạnh, đỉnh đó được đưa vào kết quả.

tạo Stack rỗng
tạo danh sách đường đi rỗng

đưa đỉnh bắt đầu vào Stack

trong khi Stack chưa rỗng:

    u = đỉnh Stack

    bỏ qua những cạnh của u đã được dùng

    nếu u còn cạnh chưa dùng:

        lấy một cạnh u -> v

        đánh dấu cạnh đã dùng

        đưa v vào Stack

    ngược lại:

        đưa u vào đường đi

        xóa u khỏi Stack

đảo ngược đường đi

Nếu đồ thị có $m$ cạnh thì một đường Euler dùng hết mọi cạnh phải có:

m+1

đỉnh trong kết quả.

Đồ thị vô hướng

Mỗi cạnh vật lý nên có một mã cạnh (Edge ID) riêng.

Hai hướng của cùng một cạnh dùng chung mã đó để tránh sử dụng một cạnh hai lần.

Điều kiện bậc

Chu trình Euler vô hướng (Eulerian Circuit):

deg(v)\equiv0\pmod2

Đường đi Euler vô hướng (Eulerian Path) có đúng hai đỉnh bậc lẻ.

Chu trình Euler có hướng:

indeg(v)=outdeg(v)

Đường đi Euler có hướng từ $s$ đến $t$ :

outdeg(s)=indeg(s)+1

indeg(t)=outdeg(t)+1

Các đỉnh khác:

indeg(v)=outdeg(v)

Giai đoạn 13 - Hoàn tác, Rollback, Persistence và xử lý Offline

Hoàn tác (Undo)

Thay vì lưu toàn bộ trạng thái, ta chỉ lưu phần thay đổi cần thiết để khôi phục lại trạng thái trước.

trước khi thay đổi một giá trị:

    lưu giá trị cũ vào Stack lịch sử

    thực hiện thay đổi

Hoàn tác:

lấy thay đổi gần nhất trong Stack lịch sử

khôi phục lại giá trị cũ

xóa bản ghi đó khỏi Stack

Stack bền vững (Persistent Stack)

Mỗi node lưu:

Node=(value,parent)

Khi thêm phần tử:

tạo node mới

node mới lưu giá trị x

parent của node mới
trỏ tới đỉnh của phiên bản cũ

đỉnh của phiên bản mới
là node mới

Khi xóa đỉnh:

đỉnh mới
=
parent của đỉnh hiện tại

Mỗi lần thêm chỉ tạo một node mới nên chi phí là:

O(1)

Cây phiên bản (Version Tree)

Nếu mỗi phiên bản mới được tạo từ một phiên bản trước, các phiên bản tạo thành một cây.

khi đi từ phiên bản cha sang phiên bản con:

    áp dụng thay đổi của phiên bản con

xử lý phiên bản con

khi quay lại phiên bản cha:

    hoàn tác thay đổi vừa áp dụng

DSU Rollback

Khi nối root $b$ vào root $a$ , cần lưu lại thông tin cũ:

(b,\ parent_b,\ size_a)

tìm root a
tìm root b

nếu a và b đã cùng một tập:
    không cần nối

nếu size[a] < size[b]:
    đổi a và b

lưu lại:
    root b
    parent cũ của b
    size cũ của a

gán parent[b] = a

size[a] = size[a] + size[b]

Hoàn tác:

lấy thay đổi gần nhất

khôi phục parent của b

khôi phục size của a

xóa bản ghi khỏi Stack lịch sử

Với DSU Rollback, thường dùng gộp theo kích thước (Union by Size) và không dùng nén đường đi (Path Compression) thông thường.

Segment Tree theo thời gian (Segment Tree over Time)

Nếu một cạnh hoặc trạng thái tồn tại trong khoảng:

[l,r)

ta gắn nó vào các node của Segment Tree phủ khoảng thời gian đó.

duyệt một node của cây thời gian:

    áp dụng các thay đổi gắn với node

    nếu node là lá:
        trả lời truy vấn tại thời điểm đó

    ngược lại:
        duyệt con trái
        duyệt con phải

    hoàn tác các thay đổi đã áp dụng tại node

Mỗi khoảng thời gian được phân vào:

O(\log q)

node của cây.

Nhảy tổ tiên theo lũy thừa hai (Binary Lifting)

Gọi:

up[v][0]=parent[v]

và:

up[v][j] = up[up[v][j-1]][j-1]

Khi cần đi ngược $k$ bước:

duyệt từng bit của k:

    nếu bit j bằng 1:
        v = up[v][j]

Độ phức tạp:

O(\log n)

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
STK0000074 Giá trị nhỏ hơn gần nhất (Nearest Smaller Values)	0	0	1
STK0000075 Phần tử lớn hơn tiếp theo (Next Greater Element)	0	0	1
STK0000076 Phần tử có tần suất lớn hơn tiếp theo (Next Greater Frequency)	0	0	1
STK0000077 Tháp thu tín hiệu (Tower)	0	0	1
STK0000078 Vườn trên mái (Rooftop Garden)	0	0	1
STK0000079 Cuộc hội ngộ Oasis (Oasis Reunion)	0	0	1
STK0000080 Tầm nhìn tòa nhà (Tower Visibility)	0	0	1
STK0000081 Các tòa nhà (Buildings)	0	0	1
STK0000082 Nhiệt độ hằng ngày (Daily Temperatures)	0	0	1
STK0000083 Phần tử lớn hơn tiếp theo I (Next Greater Element I)	0	0	1
STK0000084 Phần tử lớn hơn tiếp theo II (Next Greater Element II)	0	0	1
STK0000085 Cây nhiễm độc (Poisonous Plants)	0	0	1
STK0000086 Hàng đợi (Queue)	0	0	1
STK0000087 XOR cực đại thứ cấp (Maximum Xor Secondary)	0	0	1

Người tham gia: 1
Tạo bởi: Phước Hưng

LỘ TRÌNH STACK

Giai đoạn 1 - Stack cơ bản, LIFO và giảm chuỗi

Giai đoạn 2 - Ngoặc và cấu trúc lồng nhau (Nesting)

Ngoặc một loại

Nhiều loại ngoặc

Giai đoạn 3 - Biểu thức và phân tích cú pháp (Expression Parsing)

Biểu thức hậu tố (Postfix)

Độ ưu tiên toán tử (Precedence)

Giai đoạn 4 - Hai Stack và thay đệ quy bằng Stack

Hàng đợi bằng hai Stack (Queue using Two Stacks)

Trình soạn thảo bằng hai Stack

Thay đệ quy bằng Stack (Recursion-to-Stack)

Giai đoạn 5 - Min Stack, Max Stack và Stack có giá trị tổng hợp

Min Stack

Max Stack

Stack tổng hợp (Aggregate Stack)

Giai đoạn 6 - Stack đơn điệu (Monotonic Stack)

Phần tử nhỏ hơn gần nhất bên trái (Previous Smaller)

Phần tử nhỏ hơn gần nhất bên phải (Next Smaller)

Phần tử lớn hơn gần nhất bên phải (Next Greater)

Giai đoạn 7 - Histogram và hình chữ nhật lớn nhất

Từ ma trận về Histogram

Giai đoạn 8 - Đếm đóng góp (Contribution Counting)

Tổng giá trị nhỏ nhất của mọi đoạn con (Sum of Subarray Minimums)

Tổng giá trị lớn nhất của mọi đoạn con (Sum of Subarray Maximums)

Giai đoạn 9 - Cây Cartesian (Cartesian Tree)

Giai đoạn 10 - Stack kết hợp Quy hoạch động (DP) và Tham lam (Greedy)

Stack kết hợp Quy hoạch động (Dynamic Programming)

Stack tham lam (Greedy Monotonic Stack)

Giai đoạn 11 - Stack trong DFS và đồ thị

DFS không đệ quy (Iterative DFS)

DFS cần biết thời điểm đi vào và đi ra

Low-link

Giai đoạn 12 - Đường đi Euler và Hierholzer

Đồ thị vô hướng

Điều kiện bậc

Giai đoạn 13 - Hoàn tác, Rollback, Persistence và xử lý Offline

Hoàn tác (Undo)

Stack bền vững (Persistent Stack)

Cây phiên bản (Version Tree)

DSU Rollback

Segment Tree theo thời gian (Segment Tree over Time)

Nhảy tổ tiên theo lũy thừa hai (Binary Lifting)

Phần 6. MONOTONIC STACK: NEXT/PREV GREATER/SMALLER

Mở

Trạng thái

Phát triển

Hỗ trợ

Giới thiệu

Chưa có tài khoản?

ĐĂNG NHẬP