155. Min Stack
Tags:
Medium
Skills:
Stack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Để thiết kế một stack hỗ trợ lấy phần tử nhỏ nhất trong O(1), bạn nên dùng hai stack:
Approach
Solution
1class MinStack {
2 stack: number[];
3 min_stack: number[];
4
5 constructor() {
6 this.stack = [];
7 this.min_stack = [Infinity]
8 }
9
10 push(val: number): void {
11 this.stack.push(val);
12 this.min_stack.push(Math.min(val, this.min_stack.at(-1)));
13 }
14
15 pop(): void {
16 this.stack.pop();
17 this.min_stack.pop();
18 }
19
20 top(): number {
21 return this.stack.at(-1)
22 }
23
24 getMin(): number {
25 return this.min_stack.at(-1)
26 }
27}
28
29/**
30 * Your MinStack object will be instantiated and called as such:
31 * var obj = new MinStack()
32 * obj.push(val)
33 * obj.pop()
34 * var param_3 = obj.top()
35 * var param_4 = obj.getMin()
36 */Ví dụ:
[5,[3][7], min stack sẽ chứa [5,[3][3] (vì 3 là nhỏ nhất từ đầu đến khi push 7).[5,[3][3][2].Như vậy, min stack luôn lưu trữ giá trị nhỏ nhất tương ứng với từng trạng thái của stack chính, giúp thao tác getMin() luôn là O(1)