155. Min Stack

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/min-stack/description/

Table of Contents

1. Cách tiếp cận vấn đề

Bài toán yêu cầu chúng ta thiết kế class MinStack với tính chất LIFO (last in first out) và hỗ trợ các thao tác như 1 stack bình thường: push(value), pop(), top(), kèm theo đó là một phương thức đặc biệt giúp lấy ra phần tử có giá trị min ở thời điểm hiện tại là getMin(). Và tất cả phương thức trên được yêu cầu phải được cài đặt với độ phức tạp là O(1).

Đối với các thao tác push, pop, top, ta hoàn toàn có thể tận dụng lại từ thư viện có sẵn với O(1) vì bài toán không yêu cầu ta phải implement 1 cách thủ công Stack. Tuy nhiên đối với phương thức getMin() thì không có sẵn vì vậy ta cần phải tìm cách để cài đặt nó với độ phức tạp O(1).

Cách tiếp cận đơn giản nhất chính là việc ta sẽ có 1 biến để lưu lại giá trị min, và mỗi lần chúng ta push 1 phần tử mới vào stack, ta sẽ cập nhật lại giá trị min nếu giá trị được push đó nhỏ hơn min. Tuy nhiên đó chỉ là suy nghĩ một chiều vì chúng ta còn 1 thao tác nữa là pop(): khi pop 1 phần tử ra khỏi stack, phần tử đó hoàn toàn có thể là phần tử min và chúng ta cần tìm phần tử min tiếp theo trong những phần tử hiện tại của stack:

• Để làm được điều này thì mỗi lần ta push 1 phần tử vào stack ta cũng sẽ lưu nó vào 1 mảng phụ nữa tạm gọi là array value[]
• Và khi thực hiện theo tác pop() ta có thể duyệt qua các phần tử của value[] và tìm ra phần tử min tiếp theo -> O(n)

Như vậy ta đã xác định được độ khó của bài toán nằm ở chỗ làm sao khi pop 1 phần tử ra khỏi stack, ta có thể tìm ra được phần tử min tiếp theo với độ phức tạp là O(1).

2. Solution & Phân Tích

Để làm được điều đã nêu ở mục 1, ta sẽ sử dụng cấu trúc dữ liệu monotonic stack - là 1 stack sẽ đảm bảo lưu các phần tử theo thứ tự tăng dần hoặc giảm dần (Đối với bài toán này thì cần stack giảm dần).

• Điều đó có nghĩa là mỗi lần ta push một phần tử vào stack, ta sẽ push phần tử min hiện tại vào monotonic stack luôn.
• Và giá trị top của monotonic stack sẽ là giá trị cần trả về cho phương thức getMin() (giá trị min hiện tại).
• Mỗi lần ta pop 1 phần tử ra khỏi stack, ta cũng sẽ pop phần tử trong monotonic stack, như vậy sẽ luôn đảm bảo phần tử top của monotonic stack luôn là phần tử nhỏ nhất hiện tại.

Time-Complexity: O(1) cho tất cả method

Space-Complexity: O(n)

Với n là số lượng các phần tử push tối đa vào trong stack.

3. Code