Cách giải dễ nhất

Điều đầu tiên ta nghĩ đến sẽ là tạo một biến để chứa giá trị cực tiểu (hay cực đại). Khi push vào, ta sẽ cập nhật lại biến này nếu cần. Khi hỏi min thì ta chỉ cần trả về giá trị này.

Vấn đề phức tạp là khi pop ra, làm sao để ta cập nhật lại biến cực tiểu đó? Một cách rất đơn giản là ta sẽ duyệt lại toàn bộ các dữ liệu đang có trong ngăn xếp để đưa ra giá trị cực tiểu mới.

Cách giải này dẫn đến độ phức tạp O(1) cho push, O(1) cho min và O(n) cho pop.

class Stack(object):

    def __init__(self):
        self.store = []
        self.min = None

    def push(self, value):
        self.store.append(value)
        if self.min is None or self.min < value:
            self.min = value

    def pop(self):
        r = self.store[-1]
        del self.store[-1]
        if not self.store:
            self.min = None
        else:
            self.min = min(self.store)
        return r

    def min(self):
        return self.min

Cách giải O(1) cho pop

Ta nhận thấy rằng tác vụ pop có độ phức tạp O(n) là bởi vì ta phải duyệt lại toàn bộ các phần tử hiện tại của ngăn xếp để xác định phần tử cực tiểu.

Một phương pháp thường được sử dụng để tăng tốc tác vụ là sử dụng bộ nhớ tạm (cache). Ta sẽ tráo đổi giữa thời gian chạy, và không gian nhớ. Nếu như ở mỗi lần push, ta lưu giá trị cực tiểu của các phần tử trong ngăn xếp này vào trong một ngăn xếp thứ hai, thì khi trả lời min, ta chỉ việc nhìn vào (peek) ngăn xếp thứ hai là sẽ có ngay kết quả. Và khi pop thì ta chỉ việc pop ở cả hai ngăn xếp. Các tác vụ này đều có độ phức tạp O(1), nhưng ta sẽ tốn thêm O(n) bộ nhớ cho ngăn xếp thứ hai.

class StackBase(object):

    def __init__(self):
        self.store = []

    def push(self, value):
        self.store.append(value)

    def pop(self):
        r = self.store[-1]
        del self.store[-1]
        return r

    def peek(self):
        return self.store[-1]

    def __bool__(self):
        return bool(self.store)


class StackWithMin(object):

    def __init__(self):
        self.store = StackBase()
        self.mins = StackBase()

    def push(self, value):
        self.store.push(value)
        if not self.mins or self.mins.peek() < value:
            self.mins.push(value)
        else:
            self.mins.push(self.min.peek())

    def pop(self):
        self.mins.pop()
        return self.store.pop()

    def min(self):
        return self.mins.peek()

Cách giải O(1) cho pop cải tiến

Cách giải trên tráo đổi O(1) bộ nhớ và O(n) thời gian cho O(n) bộ nhớ và O(1) thời gian.

Vấn đề dẫn đến O(n) bộ nhớ là do ở mỗi lần push ta cũng lưu lại giá trị cực tiểu của các phần tử hiện tại. Nếu như ta chỉ lưu vị trí của phần tử cực tiểu, thì ta sẽ tiết kiệm được bộ nhớ một chút. Ta chỉ cần lưu lại vị trí của phần tử cực tiểu mới, nếu vị trí này khác với vị trí hiện tại. Khi pop ra, nếu số lượng phần tử hiện tại ít hơn vị trí của phần tử cực tiểu thì ta cũng pop luôn vị trí này ra khỏi ngăn xếp thứ hai. Điều này đảm bảo điều kiện bất biến vị trí của phần tử cực tiểu luôn luôn nhỏ hơn số lượng phần tử trong ngăn xếp.

Cài đặt này xin được để dành làm một thử thách nhỏ cho bạn đọc. Diễn đàn là nơi tốt nhất để bạn đọc trao đổi thêm.