Monotonic stack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
Monotonic stack là gì?
Monotonic stack (stack đơn điệu) là một DSA đặc biệt dựa trên stack, được thiết kế để lưu trữ các phần tử theo thứ tự tăng dần hoặc giảm dần. Cấu trúc này thường được sử dụng để tối ưu hóa các bài toán liên quan đến việc tìm phần tử lớn nhất hoặc nhỏ nhất gần kề trong một dãy số, giảm độ phức tạp từ O(n^2) xuống O(n)
Nguyên lý hoạt động
Implement: Decrease monotonic stack → dùng để tìm next greater element
1stack = [7,8,9]1function nextGreaterElement(arr: number[]): number[] {
2 const stack: number[] = [];
3 const result: number[] = new Array(arr.length).fill(-1);
4
5 for(let i = 0; i < arr.length; i++) {
6 while(stack.length > 0 && arr[stack.at(-1)] < arr[i]) {
7 const index = stack.pop();
8 result[index] = arr[i];
9 }
10
11 stack.push(i);
12 }
13
14 return result;
15}
16
17console.log(nextGreaterElement([2, 1, 5, 3, 6, 4, 8]));
18// Output: [5, 5, 6, 6, 8, 8, -1]Implement: Increase monotonic stack → Dùng để tìm next smaller element
1stack = [9,8,7]1function nextSmallerElement(arr: number[]): number[] {
2 const stack: number[] = [];
3 const result: number[] = new Array(arr.length).fill(-1);
4
5 for (let i = 0; i < arr.length; i++) {
6 // Nếu phần tử hiện tại nhỏ hơn phần tử ở đỉnh stack, cập nhật kết quả
7 while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
8 const index = stack.pop()!;
9 result[index] = arr[i];
10 }
11 // Đẩy chỉ số của phần tử hiện tại vào stack
12 stack.push(i);
13 }
14
15 return result;
16}
17
18// Ví dụ sử dụng
19console.log(nextSmallerElement([4, 5, 2, 10, 8]));
20// Output: [2, 2, -1, 8, -1]
21