Thiết kế Min Stack — trả về phần tử nhỏ nhất trong O(1), làm sao mà không quét lại?

Ý tưởng: Dùng stack phụ lưu giá trị min tại từng thời điểm. Mỗi lần push, đẩy thêm min(value, đỉnh stack min hiện tại) vào stack min. Khi pop thì pop cả hai. getMin() chỉ là đọc đỉnh stack min — O(1).

Hình dung: mỗi tầng của stack mang theo một tấm nhãn ghi "min của mọi thứ từ đây trở xuống" — gỡ tầng nào thì nhãn của tầng đó biến mất theo.

class MinStack {
  private stack: number[] = []
  private mins: number[] = []
  push(val: number): void {
    this.stack.push(val)
    const min = this.mins.length ? Math.min(val, this.mins.at(-1)!) : val
    this.mins.push(min)
  }
  pop(): void { this.stack.pop(); this.mins.pop() }
  top(): number { return this.stack.at(-1)! }
  getMin(): number { return this.mins.at(-1)! }
}

Độ phức tạp: mọi thao tác O(1) thời gian; bộ nhớ O(n) phụ.

Lưu ý: Cách tối ưu bộ nhớ hơn là chỉ push vào stack min khi gặp giá trị <= min hiện tại, nhưng phải cẩn thận với giá trị trùng — cách "luôn push" trên an toàn và dễ đúng trong phỏng vấn.