Monotonic Stack & Queue: Tìm phần tử lớn hơn hoặc nhỏ hơn tiếp theo trong O(N)
Hướng dẫn Monotonic Stack và Queue bằng TypeScript: next/previous greater-smaller element, circular array, histogram, deque và chứng minh O(N) amortized.
ShanverseCập nhật 11 phút đọc— lượt xemĐang tải lượt xem
Data Structures
Algorithms
Vấn đề: vì sao brute force là O(N²)?
Với mỗi phần tử, tìm phần tử lớn hơn đầu tiên ở bên phải:
Trong trường hợp xấu nhất như mảng giảm dần, gần như mọi suffix đều bị quét lại: O(N²).
Monotonic Stack giữ các index chưa tìm thấy đáp án, theo một thứ tự đảm bảo phần tử mới có thể giải quyết nhiều index cùng lúc.
“Monotonic” nghĩa là gì?
Một stack/queue monotonic giữ value theo thứ tự tăng hoặc giảm.
Decreasing stack: value từ đáy đến đỉnh giảm dần hoặc không tăng.
Bình luận
Increasing stack: value từ đáy đến đỉnh tăng dần hoặc không giảm.
Tên gọi dễ gây nhầm vì có tài liệu mô tả theo thứ tự nhìn từ top xuống. Đừng học thuộc tên; hãy viết rõ invariant:
hoặc:
Tại sao nên lưu index?
Lưu index thay vì value giúp:
Tính khoảng cách: currentIndex - previousIndex.
Phân biệt duplicates.
Xác định width của histogram.
Loại phần tử đã ra khỏi Sliding Window.
Trả kết quả theo vị trí input.
Value luôn có thể lấy bằng numbers[index].
Next Greater Element bên phải
Ví dụ:
Invariant
Sau mỗi vòng:
Stack chứa các index chưa có next greater.
Value từ đáy đến đỉnh là không tăng.
Khi value mới lớn hơn top, nó là phần tử lớn hơn đầu tiên của top vì mọi vị trí giữa hai index đã được xử lý nhưng không đủ lớn.
Trả về index hoặc khoảng cách
Khoảng cách có thể ghi bằng index - resolvedIndex.
Strict hay non-strict?
Một ký tự so sánh thay đổi định nghĩa:
Next strictly greater: pop khi top < current.
Next greater or equal: pop khi top <= current.
Next strictly smaller: pop khi top > current.
Next smaller or equal: pop khi top >= current.
Với duplicates, < và <= cho kết quả khác nhau. Phải đọc đúng cụm “greater”, “greater or equal”, “smaller” hay “smaller or equal”.
Bốn hướng cơ bản
Có hai cách tư duy:
Current resolves stack: phần tử hiện tại là đáp án cho các index cũ.
Stack answers current: loại candidate không hợp lệ, rồi top là đáp án gần nhất của current.
Không trộn hai template mà không xác định output.
Previous Smaller Element
Sau vòng while, top là index gần nhất bên trái có value nhỏ hơn strict.
Daily Temperatures
Tìm số ngày phải chờ đến nhiệt độ cao hơn:
Stack chứa những ngày chưa gặp nhiệt độ cao hơn, theo nhiệt độ không tăng.
Circular Next Greater Element
Với mảng vòng tròn, scan logic 2N vị trí nhưng chỉ push index trong lượt đầu:
Nếu push trong cả hai lượt, cùng index có thể xuất hiện nhiều lần và làm logic/memory phức tạp không cần thiết.
Largest Rectangle in Histogram
Đây là ứng dụng quan trọng của previous/next smaller boundary.
Sentinel height 0 ở cuối buộc xử lý hết stack. Khi pop bar tại heightIndex:
index là first smaller bên phải.
Top mới là previous smaller bên trái.
Width là right - left - 1.
Duplicates trong histogram
Dùng > hay >= quyết định cách giữ các cột bằng nhau. Nhiều biến thể đều đúng nếu boundary semantics nhất quán, nhưng trộn strict/non-strict giữa hai phía có thể đếm sai width.
Monotonic Queue là gì?
Monotonic Queue thường được cài bằng deque. Nó cần:
Xóa đầu khi index hết hạn khỏi cửa sổ.
Xóa cuối khi candidate bị phần tử mới chi phối.
Đọc đầu để lấy max/min hiện tại.
Monotonic Stack giải nearest greater/smaller theo quan hệ vị trí. Monotonic Queue nổi bật trong fixed-size Sliding Window.
Sliding Window Maximum trong O(N)
Invariant của deque
Index từ đầu đến cuối tăng dần.
Value từ đầu đến cuối giảm dần.
Mọi index đều còn nằm trong cửa sổ.
Đầu deque luôn là maximum hiện tại.
Một value nhỏ hơn ở phía sau phần tử mới sẽ hết hạn sớm hơn mà không bao giờ thắng, nên có thể xóa vĩnh viễn.
Sliding Window Minimum
Đổi điều kiện loại đuôi:
Deque trở thành increasing; đầu là minimum.
Vì sao không dùng Array.shift()?
shift() có thể phải dời lại các phần tử còn lại, làm mỗi lần xóa đầu tốn O(K). Dùng biến head, ring buffer hoặc deque implementation thực sự để giữ O(1) amortized.
Việc splice() compact thỉnh thoảng trong ví dụ vẫn có thể amortize, nhưng production có throughput cao nên dùng ring buffer/deque rõ ràng.
Chứng minh O(N) amortized
Có vòng while lồng trong for, nhưng:
Mỗi index được push một lần.
Mỗi index bị pop tối đa một lần.
Với queue, mỗi index cũng hết hạn khỏi đầu tối đa một lần.
Tổng số thao tác stack/deque tỷ lệ với N, không phải N².
amortized nghĩa là một iteration có thể pop nhiều phần tử, nhưng tổng trên toàn bộ input vẫn tuyến tính.
Monotonic Queue hay Heap?
Deque thắng khi chỉ cần max/min và cửa sổ di chuyển theo thứ tự. Nó không thay thế cấu trúc hỗ trợ median hay arbitrary deletion.
Template tư duy
Current resolves previous indices
Stack answers current index
Monotonic deque
Lỗi thường gặp
1. Lưu value thay vì index
Sẽ khó tính distance, expiry, width và xử lý duplicates.
2. Sai < và <=
Đây là lỗi phổ biến nhất. Viết test có duplicates trước khi chọn comparator.
3. Không xác định nearest hay bất kỳ
Monotonic Stack thường trả phần tử thỏa điều kiện đầu tiên/gần nhất theo hướng scan. Nếu bài cần global maximum suffix, prefix/suffix preprocessing có thể đơn giản hơn.
4. Đọc top sau khi stack rỗng
Luôn kiểm tra stack.length > 0.
5. Push sentinel index rồi đọc ngoài mảng
Trong histogram, code trên push index sentinel sau khi đã flush. Không được đọc heights[sentinelIndex] ở vòng sau. Vì sentinel ở iteration cuối nên an toàn; nếu thay cấu trúc loop phải xử lý rõ.
6. Circular scan push hai lần
Chỉ push trong lượt đầu trừ khi đã chứng minh biến thể khác.
7. Quên expire deque
Index cũ có thể vẫn là max nhưng đã nằm ngoài cửa sổ.
8. Xóa đuôi sai chiều
Max queue giữ value giảm dần; min queue giữ tăng dần.
9. Dùng shift() trong hot path
Có thể phá hiệu năng tuyến tính thực tế.
10. Gọi mọi stack có thứ tự là O(N)
O(N) chỉ đúng nếu mỗi phần tử được push/pop hữu hạn lần và thao tác nền là O(1) amortized.
Edge cases cần test
Input rỗng và một phần tử.
Tăng hoàn toàn.
Giảm hoàn toàn.
Mọi phần tử bằng nhau.
Duplicates xen kẽ.
Số âm và 0.
k=1, k=N, k=0, k>N.
Circular array có một phần tử.
Histogram toàn 0 hoặc cùng chiều cao.
Strict và non-strict expected outputs.
Distance so với value/index output.
Large input để phát hiện shift() hoặc thuật toán vô tình O(N²).
Cách giải bài Monotonic Stack/Queue
Xác định cần next/previous, left/right.
Xác định greater/smaller và strict/non-strict.
Chọn output: value, index, distance, count hay boundary.
Viết invariant value order của stack/deque.
Quyết định current giải quyết stack hay stack trả lời current.
Lưu index trừ khi có lý do rõ ràng.
Với queue, expire index trước khi đọc đáp án.
Viết test duplicates để chọn comparator.
Chứng minh mỗi index chỉ push/pop hữu hạn lần.
So sánh với brute force trên random input nhỏ.
Bài tập gợi ý
Next Greater Element I/II.
Daily Temperatures.
Online Stock Span.
Largest Rectangle in Histogram.
Maximal Rectangle.
Trapping Rain Water với stack.
Sum of Subarray Minimums.
Remove K Digits.
Sliding Window Maximum.
Shortest Subarray with Sum at Least K với prefix sum + monotonic deque.
Kết luận
Monotonic Stack/Queue hoạt động bằng cách xóa candidate đã bị chi phối:
Kỹ thuật đạt O(N) amortized vì mỗi index chỉ vào và ra cấu trúc một số lần hữu hạn. Thành công phụ thuộc vào bốn quyết định: hướng scan, thứ tự monotonic, comparator strict/non-strict và việc lưu index. Khi invariant được viết rõ, Next Greater/Smaller, histogram và Sliding Window Maximum trở thành cùng một mô hình thay vì các mẹo rời rạc.
Mục lục(39)
Codetypescript
1functionnextGreaterBruteForce(numbers:readonlynumber[]):number[] {2constresult=Array(numbers.length).fill(-1);34for (let index =0; index < numbers.length; index++) {5for (let next = index +1; next < numbers.length; next++) {6if (numbers[next] > numbers[index]) {7 result[index] = numbers[next];8break;9 }10 }11 }1213return result;14}
Hướng dẫn Fast & Slow Pointers và Floyd’s Cycle Detection bằng TypeScript: phát hiện cycle, tìm entry, cycle length, functional graph và các giới hạn thực tế.
Hướng dẫn Trie (Prefix Tree) để xây dựng Search Suggestion và Autocomplete: TypeScript, top-K ranking, Unicode normalization, radix tree và production architecture.
