Dùng ngăn xếp để xử lý thứ tự gần nhất

Lan kiểm tra một chuỗi gồm sáu dấu ngoặc ([{}]) trong bài thi lập trình. Mỗi dấu đóng phải khớp với dấu mở gần nhất chưa được đóng. Nếu chỉ đếm số dấu mở và đóng, Lan vẫn có thể bỏ sót chuỗi sai ([)]. Một ngăn xếp giúp bạn theo dõi đúng thứ tự cần khớp.

Ngăn xếp chỉ thêm và lấy tại một đầu

Hãy tưởng tượng một chồng sách. Cuốn đặt sau cùng nằm trên cùng và được lấy ra trước. Ngăn xếp (stack) áp dụng quy tắc vào sau ra trước (last in, first out, viết tắt LIFO). Đầu được thao tác gọi là đỉnh (top). Những phần tử bên dưới chỉ lộ ra sau khi phần tử phía trên bị lấy đi.

Trong Python, một list có thể làm ngăn xếp. Ta chọn cuối danh sách làm đỉnh, dùng append(x) để thêm và pop() để lấy. st[-1] cho biết đỉnh mà không lấy nó ra.

Ví dụ này thêm ba số rồi lấy một số. Bạn quan sát đỉnh trước và sau khi lấy:

st = []
st.append(10)
st.append(20)
st.append(30)
print(st[-1])
print(st.pop())
print(st[-1])
print(st)

30
30
20
[10, 20]

Số 30 được lấy trước dù được thêm sau. Việc đọc đỉnh không thay đổi st, còn pop() vừa trả về phần tử vừa xóa nó. Nếu cần giữ giá trị đã lấy, bạn có thể gán x = st.pop().

Một ngăn xếp rỗng không có đỉnh. Đoạn sau cố ý lấy từ danh sách rỗng để bạn thấy lỗi thật:

st = []
print(st.pop())

IndexError: pop from empty list

Python báo IndexError. Kiểm tra if st: trước khi lấy hoặc đọc đỉnh. Nhánh rỗng phải làm theo yêu cầu của đề, chẳng hạn bỏ qua thao tác hoặc in EMPTY.

Bạn có thể kết hợp các thao tác để mô phỏng một lịch sử nhỏ. Giả sử thao tác thêm được ghi push, còn thao tác lấy được ghi pop. Sau push 5, push 8, pop, push 3, thứ tự trong ngăn xếp là 5 rồi 3. Số 8 không trở lại khi ta thêm số 3. Lần lấy kế tiếp sẽ trả về 3, sau đó mới tới 5.

st = []
if st:
    print(st[-1])
else:
    print("EMPTY")
st.append(7)
if st:
    print(st[-1])

EMPTY
7

Các thao tác ở cuối list có chi phí trung bình O(1). Với q thao tác, tổng thời gian trung bình là O(q) và bộ nhớ tối đa O(q). Thêm hoặc xóa ở đầu danh sách phải dịch các phần tử còn lại, nên không phù hợp để mô phỏng đỉnh này.

Dấu đóng phải khớp dấu mở gần nhất chưa đóng

Một chuỗi ngoặc hợp lệ có thể gồm ba loại (), [] và {}. Mỗi dấu đóng cần cùng loại với dấu mở gần nhất còn chờ. Các cặp có thể nằm cạnh nhau hoặc lồng vào nhau. Chẳng hạn ([]) hợp lệ, nhưng ([)] không hợp lệ dù số dấu mở và đóng bằng nhau.

Ta duyệt từ trái sang phải. Gặp dấu mở thì thêm vào ngăn xếp. Gặp dấu đóng thì so với đỉnh. Nếu ngăn xếp rỗng hoặc sai loại, chuỗi sai ngay. Nếu khớp, lấy dấu mở đó ra. Sau khi duyệt, chuỗi chỉ hợp lệ khi không còn dấu mở chưa đóng.

Đoạn sau kiểm tra cả ngoặc lồng, đóng sai thứ tự và thiếu dấu đóng. Dữ liệu chỉ gồm sáu ký tự ngoặc:

def valid(s):
    st = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            st.append(ch)
        else:
            if not st or st[-1] != pairs[ch]:
                return False
            st.pop()
    return not st

for sample in ['([])', '([)]', '(()', '']:
    print(repr(sample), valid(sample))

'([])' True
'([)]' False
'(()' False
'' True

Trong ([)], dấu ) gặp dấu [ ở đỉnh. Nó không được ghép với ( bên dưới, vì như vậy hai cặp sẽ giao nhau. Trong ((), dấu ( còn lại khiến kết quả sai. Chuỗi rỗng hợp lệ nếu đề cho phép nó.

Bảng sau diễn giải chuỗi ([]) mà không dùng cú pháp ngoặc dễ gây nhầm trong bảng Markdown. Cột cuối ghi ngăn xếp từ đáy sang đỉnh sau khi xử lý từng dấu.

Nếu đề chỉ cho một loại ngoặc, một biến đếm cũng có thể kiểm tra độ sâu. Nhưng với nhiều loại, cùng độ sâu chưa cho biết loại ngoặc ở đỉnh. Ví dụ, hai tiền tố ([ và (( đều có hai dấu mở chưa ghép. Dấu ] chỉ phù hợp với tiền tố đầu. Ngăn xếp giữ được thông tin cần phân biệt hai trường hợp này.

Bất biến (invariant) là điều đúng sau mỗi bước xử lý. Ở đây, ngăn xếp chứa đúng các dấu mở chưa được ghép, theo thứ tự xuất hiện. Khi gặp dấu đóng, mọi dấu mở ở trên đỉnh đều đã được ghép. Vì vậy chỉ đỉnh có thể là bạn ghép hợp lệ tiếp theo. Kiểm tra đỉnh và kiểm tra rỗng cuối chuỗi là đủ.

Với chuỗi dài n, mỗi ký tự được xét một lần. Mỗi dấu mở được thêm một lần và lấy tối đa một lần. Thời gian O(n), bộ nhớ O(n) trong trường hợp toàn dấu mở. Với 100 000 ký tự, ta xử lý khoảng 100 000 lượt thay vì so mọi cặp vị trí.

Hoàn tác lấy thao tác gần nhất còn hiệu lực

Một trình soạn thảo đơn giản nhận chữ thường và dấu #. Dấu # xóa chữ cuối đang có. Khi chưa có chữ, nó không làm gì. Ngăn xếp lưu chính những chữ còn lại, nên đỉnh là chữ cần xóa tiếp theo.

s = 'ab##c#de'
st = []
for ch in s:
    if ch == '#':
        if st:
            st.pop()
    else:
        st.append(ch)
print(''.join(st))

de

Sau ab##, cả hai chữ đã bị xóa. Chữ c cũng bị dấu # tiếp theo xóa, còn de được giữ. ''.join(st) nối các ký tự theo đúng thứ tự từ đáy đến đỉnh. Nếu đề yêu cầu một ký hiệu riêng cho kết quả rỗng, cần xử lý trước khi in.

Sau mỗi ký tự, st bằng đúng văn bản hiện tại. Thêm chữ làm văn bản dài thêm một ký tự. Lấy đỉnh làm mất đúng ký tự cuối. Do đó bất biến được giữ qua từng bước. Với n ký tự, thời gian trung bình O(n) và bộ nhớ O(n); phép nối cuối cũng chỉ duyệt các chữ còn lại một lần.

Một cách rút gọn khác là xóa hai chữ kề nhau giống nhau. Khi gặp chữ mới, nếu nó bằng đỉnh thì xóa đỉnh và không thêm chữ mới. Nếu khác, ta thêm nó. Việc này còn xử lý được hiệu ứng dây chuyền khi hai chữ trước đó trở nên kề nhau.

s = 'abbaca'
st = []
for ch in s:
    if st and st[-1] == ch:
        st.pop()
    else:
        st.append(ch)
print(''.join(st))

ca

Sau khi đọc abb, cặp bb đã bị xóa và đỉnh trở lại là a. Chữ a tiếp theo lại xóa đỉnh đó. Hai chữ cuối ca được giữ. Sau mỗi lượt, phần đã xử lý không còn cặp bằng nhau kề nhau. Khi thêm một chữ, chỉ cặp mới ở cuối có thể cần xóa; nếu xóa cặp ấy, phần còn lại vốn đã được rút gọn.

Kết quả không phụ thuộc vào thứ tự chọn các cặp để xóa. Hai cặp không giao nhau có thể đổi thứ tự xóa. Nếu chúng giao nhau, ba chữ liên tiếp phải giống nhau, và xóa cặp bên trái hay bên phải đều để lại cùng một chữ. Lặp lập luận này cho các bước tiếp theo cho cùng chuỗi cuối. Thuật toán vì thế tìm được kết quả đề yêu cầu, không chỉ một cách xóa tùy ý.

Ngăn xếp đơn điệu giữ các ứng viên chưa bị che

Với mỗi số trong dãy, ta muốn tìm số đầu tiên ở bên phải lớn hơn hẳn nó. Xét dãy 2, 1, 2, 4, 3: số 2 đầu tiên có đáp án 4. Số 2 ở vị trí sau không đủ lớn, nên phải tiếp tục nhìn sang phải. Số 4 không có đáp án.

Ngăn xếp đơn điệu (monotonic stack) giữ các ứng viên theo một thứ tự giá trị. Ta duyệt từ phải sang trái. Trước khi trả lời cho a[i], bỏ các giá trị ở đỉnh nhỏ hơn hoặc bằng a[i]. Đỉnh còn lại, nếu có, là giá trị lớn hơn gần nhất bên phải. Cuối cùng thêm a[i] cho các vị trí tiếp theo.

Trong đoạn mã, -1 là ký hiệu không tìm thấy. Nếu dãy cho phép số âm, -1 cũng có thể là giá trị thật; đề phải quy định cách hiểu ký hiệu đó.

a = [2, 1, 2, 4, 3]
st = []
answer = [-1] * len(a)
for i in range(len(a) - 1, -1, -1):
    while st and st[-1] <= a[i]:
        st.pop()
    if st:
        answer[i] = st[-1]
    st.append(a[i])
print(answer)

[4, 2, 4, -1, -1]

Vì sao được loại số v <= a[i]? Nó không lớn hơn a[i]. Với một vị trí còn ở bên trái, nếu v đủ lớn thì a[i] cũng đủ lớn và lại gần hơn. Do đó v không còn là đáp án gần nhất cho bất kỳ vị trí chưa xử lý nào. Các ứng viên bị bỏ trước đó cũng đã bị một ứng viên gần hơn và không nhỏ hơn che khuất.

Sau khi bỏ các phần tử không phù hợp, đỉnh là ứng viên gần nhất còn lại. Nếu ngăn xếp rỗng, không có số lớn hơn bên phải. Từ đáy đến đỉnh, các giá trị còn trong ngăn xếp giảm nghiêm ngặt sau mỗi lượt. Điều đó cho phép kiểm tra và loại liên tiếp từ đỉnh.

Với dãy 2, 1, 2, 4, 3, bảng sau ghi ngăn xếp từ đáy lên đỉnh sau từng lượt. Ta bắt đầu từ chỉ số 4 và đi về chỉ số 0.

Ở lượt cuối, số 1 bị loại trước vì nằm ở đỉnh. Sau đó số 2 bằng giá trị đang xét cũng bị loại. Số 4 còn lại là giá trị hợp lệ gần nhất. Hai số 2 xuất hiện ở các vị trí khác nhau, nên cần phân biệt số đang xét với số bị lấy.

Vòng while nằm trong vòng for nhưng không khiến tổng số lần lấy thành O(n²). Mỗi giá trị được thêm đúng một lần và bị lấy nhiều nhất một lần. Cộng cả các lượt thêm, lấy và kiểm tra, thuật toán chạy O(n) thời gian và O(n) bộ nhớ. Với n = 100 000, tối đa 100 000 lượt thêm và 100 000 lượt lấy. Duyệt lại toàn bộ đoạn bên phải cho từng vị trí có thể cần gần năm tỷ phép so sánh.

Dấu so sánh quyết định cách xử lý giá trị bằng nhau

Hai số bằng nhau là trường hợp dễ làm lộ lỗi. Khi đề yêu cầu lớn hơn, số bằng nhau không phải đáp án. Ta loại cả số nhỏ hơn lẫn số bằng, tức dùng <=. Khi đề yêu cầu lớn hơn hoặc bằng, số bằng nhau được giữ và chỉ loại số nhỏ hơn bằng <.

a = [5, 5, 6]
for allow_equal in [False, True]:
    st = []
    ans = [-1] * len(a)
    for i in range(len(a) - 1, -1, -1):
        while st and (st[-1] < a[i] if allow_equal
                      else st[-1] <= a[i]):
            st.pop()
        if st:
            ans[i] = st[-1]
        st.append(a[i])
    print(ans)

[6, 6, -1]
[5, 6, -1]

Với yêu cầu lớn hơn hẳn, số 5 đầu tiên tìm tới 6. Với yêu cầu cho phép bằng, số 5 kế bên là đáp án. Bảng sau áp dụng cho cách duyệt từ phải sang trái và loại ứng viên khỏi đỉnh trước khi trả lời:

Đừng nhớ dấu một cách tách rời đề. Hãy hỏi ứng viên bằng giá trị hiện tại có được chấp nhận không. Sau đó thử dãy hai phần tử bằng nhau để xác nhận điều kiện.

Lưu chỉ số khi cần vị trí hoặc khoảng cách

Giả sử bạn theo dõi giá mỗi ngày. Với mỗi ngày, hãy đếm số ngày liên tiếp kết thúc tại hôm đó có giá không vượt giá hiện tại. Giá 70, 50, 60, 60 cho ngày cuối một đoạn ba ngày. Ngày đầu không thuộc đoạn vì 70 lớn hơn 60.

Ta cần khoảng cách tới ngày gần nhất bên trái có giá lớn hơn hẳn. Vì vậy ngăn xếp lưu chỉ số (index), không chỉ lưu giá. Khi xét ngày i, bỏ những ngày ở đỉnh có giá nhỏ hơn hoặc bằng giá hiện tại. Ngày ở đỉnh còn lại là mốc chặn gần nhất. Nếu không còn mốc, cả i + 1 ngày đều được tính.

prices = [70, 50, 60, 60]
st = []
span = []
for i, price in enumerate(prices):
    while st and prices[st[-1]] <= price:
        st.pop()
    if st:
        span.append(i - st[-1])
    else:
        span.append(i + 1)
    st.append(i)
print(span)

[1, 1, 2, 3]

Ngày thứ tư có chỉ số 3. Hai ngày giá 60 và 50 bị loại khỏi đỉnh khi xét giá 60 cuối. Ngày giá 70 còn ở chỉ số 0, nên độ dài là 3 - 0 = 3. Dấu bằng phải được loại vì giá bằng hôm nay vẫn thuộc đoạn được đếm.

Một ngày bị loại không thể chặn một ngày tương lai phù hợp hơn ngày hiện tại. Ngày hiện tại ở gần hơn và có giá không nhỏ hơn ngày bị loại. Do đó ngăn xếp giữ đủ các mốc chặn có thể cần. Mỗi chỉ số được thêm một lần và lấy tối đa một lần, nên thời gian O(n) và bộ nhớ O(n). Với 100 000 ngày, số thao tác ngăn xếp tăng tuyến tính theo số ngày.

Chỉ số cũng giúp phân biệt hai vị trí có cùng giá trị và tính khoảng cách. Nếu đề chỉ hỏi giá trị, lưu giá trị thường đủ. Nếu đề hỏi vị trí, số bước, hoặc độ dài, hãy cân nhắc lưu chỉ số.

Nếu đề hỏi chính ngày có giá lớn hơn gần nhất bên phải, cũng có thể lưu chỉ số trong thuật toán duyệt từ phải sang trái. Khi so sánh, truy cập giá bằng a[st[-1]]. Khi có đáp án, lấy chỉ số ở đỉnh. Nếu đề đánh số ngày từ 1 thì cộng thêm 1 trước khi in.

a = [3, 1, 3, 2, 5]
st = []
answer = [-1] * len(a)
for i in range(len(a) - 1, -1, -1):
    while st and a[st[-1]] <= a[i]:
        st.pop()
    if st:
        answer[i] = st[-1] + 1
    st.append(i)
print(*answer)

5 3 5 5 -1

Ngày đầu có giá 3 và gặp giá bằng tại ngày thứ ba. Vì yêu cầu lớn hơn hẳn, đáp án của ngày đầu là ngày thứ năm. Chỉ số trong Python bắt đầu từ 0, còn đầu ra này đánh số từ 1. Việc chuyển đổi chỉ áp dụng lúc ghi đáp án; các phép truy cập a vẫn dùng chỉ số Python.

Lỗi thường gặp

Tóm tắt

• Ngăn xếp lấy phần tử thêm gần nhất còn lại. Kiểm tra rỗng trước khi lấy hoặc đọc đỉnh.
• Với ngoặc, lưu các dấu mở chưa ghép và kiểm tra đúng loại ở đỉnh.
• Với ngăn xếp đơn điệu, loại ứng viên bị phần tử gần hơn che khuất.
• Dấu so sánh phụ thuộc yêu cầu nghiêm ngặt hay cho phép bằng. Lưu chỉ số khi cần khoảng cách.
• Mỗi phần tử thêm một lần, lấy tối đa một lần nên tổng thời gian là O(n).

Kiểm tra nhanh

Đọc thêm

• Python Tutorial: Using Lists as Stacks
• Python Library Reference: Mutable Sequence Types