Min Stack
Thiết kế một ngăn xếp, ngoài các thao tác thông thường push, pop và top, còn có thể báo giá trị nhỏ nhất mà nó chứa bằng getMin. Cả bốn thao tác phải chạy trong thời gian O(1).
Bạn nhận được các thao tác theo thứ tự trong ops, trong đó args[i] chứa giá trị cần thêm bằng thao tác push và là 0 với mọi thao tác khác. Thực hiện chúng trên một ngăn xếp duy nhất, ban đầu rỗng, rồi trả về một chuỗi cho mỗi thao tác: "null" cho push và pop, còn top và getMin trả về số dưới dạng văn bản.
Hàm
- opsstring-array
- các thao tác, theo thứ tự chúng chạy
- argsinteger-array
- giá trị cho mỗi thao tác đẩy, 0 cho mọi thao tác khác
- Trả vềstring-array
- một câu trả lời cho mỗi phép toán, dưới dạng văn bản
Ràng buộc
1 ≤ ops.length ≤ 3000args.length == ops.length- Mỗi
ops[i]làpush,pop,tophoặcgetMin. -231+1 ≤ args[i] ≤ 231-1cho thao tác push vàargs[i] == 0cho mọi thao tác khác.- Chỉ gọi
pop,topvàgetMinkhi ngăn xếp có ít nhất một giá trị.
Ví dụ
- Đầu vào
- ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
- Đầu ra
- ["null", "null", "null", "1", "null", "1", "null", "4"]
- Giải thích
- Ngăn xếp chứa các giá trị 4, 1 và 7 theo thứ tự từ dưới lên trên, nên giá trị nhỏ nhất là 1. Lấy 7 ra thì 1 nằm trên cùng. Lấy cả 1 ra thì chỉ còn 4, nên giá trị nhỏ nhất trở lại là 4.
- Đầu vào
- ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
- Đầu ra
- ["null", "null", "null", "-2", "null", "-2", "null", "3"]
- Giải thích
- Giá trị nhỏ nhất, -2, được đưa vào hai lần. Lần lấy ra đầu tiên xóa một bản sao, bản còn lại vẫn ở đó, nên
getMinvẫn là -2. Chỉ sau lần lấy ra thứ hai, giá trị nhỏ nhất mới trở lại là 3.
- Đầu vào
- ops = ["push", "push", "pop", "push", "getMin", "top"]args = [2, 0, 0, 8, 0, 0]
- Đầu ra
- ["null", "null", "null", "null", "2", "8"]
- Giải thích
- 0 được đẩy vào rồi lấy ra, nên không còn được tính nữa. Khi đó, ngăn xếp chứa 2 và 8: phần tử trên cùng là 8 và giá trị nhỏ nhất là 2.
Câu hỏi mở rộng
Bạn có thể xây dựng một hàng đợi vào trước, ra trước có thể cho biết giá trị nhỏ nhất trong thời gian O(1) theo chi phí khấu hao không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Một biến lưu giá trị nhỏ nhất sẽ hoạt động cho đến khi bạn lấy giá trị nhỏ nhất đó ra. Bạn cần biết điều gì vào lúc đó, và bạn có thể ghi lại điều đó từ khi nào?
Ngăn xếp chỉ thay đổi ở đỉnh, vì vậy giá trị nhỏ nhất trong các giá trị bên dưới một độ cao bất kỳ sẽ giữ nguyên chừng nào ngăn xếp còn đầy đến độ cao đó. Hãy ghi lại giá trị nhỏ nhất khi bạn thêm phần tử vào ngăn xếp.
Giữ một ngăn xếp thứ hai bên cạnh các giá trị. Đẩy giá trị mới vào ngăn xếp đó khi nó nhỏ hơn hoặc bằng giá trị ở đầu ngăn xếp, và lấy giá trị ra khỏi ngăn xếp đó khi giá trị rời khỏi ngăn xếp chính bằng giá trị ở đầu ngăn xếp thứ hai. Khi đó, giá trị ở đầu ngăn xếp thứ hai luôn là đáp án cho
getMin.
Lời giải
Một ngăn xếp thông thường đã thực hiện push, pop và top trong O(1). Ngăn xếp chỉ thay đổi ở đỉnh, nên khi một giá trị nằm ở một độ cao nào đó, giá trị nhỏ nhất của mọi phần tử tính đến độ cao đó đã cố định. Ghi lại giá trị nhỏ nhất ấy khi thêm phần tử, rồi thao tác lấy phần tử ra sẽ khôi phục giá trị nhỏ nhất trước đó mà không tốn thêm chi phí.
Quét ngăn xếp mỗi khi gọi getMin
Ý tưởng
Trả lời getMin bằng cách quét mọi giá trị đã lưu. Cách này luôn chính xác vì đọc nội dung thực tế, nhưng gọi getMin với n giá trị sẽ đọc cả n giá trị. Với 1,500 lần đẩy, mỗi lần đều theo sau bởi một lần gọi getMin, cách này cần đọc hơn một triệu lần, trong khi các cách khác chỉ đọc một lần cho mỗi lần gọi.
Chỉ lưu một giá trị nhỏ nhất không giải quyết được vấn đề. Khi bạn lấy giá trị đó ra, bạn cần quét để tìm giá trị nhỏ tiếp theo.
Thuật toán
- Lưu các giá trị trong một danh sách dùng làm ngăn xếp.
- Với
push x, thêmxvào cuối danh sách; vớipop, xóa giá trị cuối cùng; vớitop, đọc giá trị đó. - Với
getMin, duyệt qua mọi giá trị đã lưu và trả về giá trị nhỏ nhất. - Ghi lại mỗi câu trả lời dưới dạng văn bản rồi trả về danh sách.
class MinStack:
def __init__(self):
self.values = []
def push(self, x):
self.values.append(x)
def pop(self):
self.values.pop()
def top(self):
return self.values[-1]
def getMin(self):
# Look at every stored value: O(n).
smallest = self.values[0]
for v in self.values:
if v < smallest:
smallest = v
return smallest
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return resultLưu giá trị nhỏ nhất bên cạnh mỗi giá trị
Ý tưởng
Giữ thêm một ngăn xếp thứ hai mins, trong đó mins[i] là giá trị nhỏ nhất trong values[0..i]. Khi thêm một giá trị vào ngăn xếp, hãy lưu giá trị nhỏ hơn giữa x và phần tử bên dưới nó. Khi lấy một giá trị ra, hãy xóa phần tử trên cùng của cả hai ngăn xếp, và phần tử trên cùng của mins lại là giá trị nhỏ nhất trong các giá trị còn lại. Trong ví dụ đầu tiên, các lần thêm 4, 1 và 7 lưu các giá trị nhỏ nhất lần lượt là 4, 1 và 1; lấy 7 rồi 1 ra sẽ còn lại 4.
Mỗi thao tác chỉ tác động đến phần tử trên cùng của hai ngăn xếp, nên mỗi thao tác có độ phức tạp O(1). Đổi lại, mỗi giá trị cần thêm một số thứ hai.
Thuật toán
- Giữ hai ngăn xếp có chiều cao bằng nhau,
valuesvàmins. - Với
push x, đưaxvàovalues, rồi đưa vàominsgiá trị nhỏ hơn giữaxvà giá trị ở đỉnh ngăn xếp (xnếuminsrỗng). - Với
pop, lấy phần tử khỏi cả hai ngăn xếp. - Với
top, đọc giá trị ở đỉnhvalues; vớigetMin, đọc giá trị ở đỉnhmins. - Ghi lại từng câu trả lời dưới dạng văn bản rồi trả về danh sách.
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # mins[i] is the smallest of values[0..i]
def push(self, x):
self.values.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.values.pop()
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return resultNgăn xếp lưu các giá trị nhỏ nhất, chỉ tăng khi xuất hiện giá trị nhỏ nhất mới
Ý tưởng
Trong cách tiếp cận thứ hai, mins thường lặp lại giá trị: đẩy 1, 7, 8 và 9 vào thì nó chứa 1, 1, 1, 1. Vì vậy, chỉ ghi một giá trị vào mins khi giá trị đó trở thành nhỏ nhất, tức là khi mins trống hoặc x nhỏ hơn hoặc bằng phần tử trên cùng của nó, đồng thời lấy phần tử khỏi mins khi chính giá trị đó rời khỏi values.
Phần tử trên cùng của mins luôn là giá trị nhỏ nhất: mọi giá trị được đẩy vào sau nó đều lớn hơn, hoặc nhỏ hơn hoặc bằng nó và được ghi vào mins, trong trường hợp đó giá trị ấy đã bị lấy ra. Dùng <= để mỗi lần xuất hiện của giá trị nhỏ nhất đều có mục riêng. Cả bốn thao tác đều giữ độ phức tạp O(1), và mins chỉ cao bằng values khi các giá trị lần lượt đến từ lớn nhất đến nhỏ nhất.
Thuật toán
- Duy trì một ngăn xếp
valuesvà một ngăn xếpmins. - Với
push x, đẩyxvàovalues. Nếuminsrỗng hoặcxnhỏ hơn hoặc bằng phần tử trên cùng của nó, đẩyxvàomins. - Với
pop, lấy một phần tử ra khỏivalues. Nếu giá trị vừa lấy ra bằng phần tử trên cùng củamins, cũng lấy một phần tử ra khỏimins. - Với
top, đọc phần tử trên cùng củavalues; vớigetMin, đọc phần tử trên cùng củamins. - Ghi lại mỗi câu trả lời dưới dạng văn bản rồi trả về danh sách.
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # each value that was a minimum when pushed; the top is the current minimum
def push(self, x):
self.values.append(x)
# <= keeps one copy per equal minimum, so popping one leaves the others.
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
def pop(self):
if self.values.pop() == self.mins[-1]:
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result
Lỗi thường gặp và trường hợp biên
- Chỉ ghi nhận giá trị nhỏ nhất mới khi
xnhỏ hơn nghiêm ngặt. Trong ví dụ thứ hai, hai giá trị -2 giống nhau dùng chung một mục trongmins, lần gọipopđầu tiên xóa mục đó, vàgetMintrả về 3 dù -2 vẫn còn trên ngăn xếp. - Gọi
poptrênminsmỗi lần gọipoptrong cách tiếp cận thứ ba. Chỉ thu nhỏ danh sách này khi giá trị bị xóa bằng giá trị ở đầu danh sách. - So sánh các số nguyên được đóng gói trong Java bằng
Integer == Integer. Cách này kiểm tra danh tính đối tượng, đúng với các giá trị được lưu trong bộ nhớ đệm từ -128 đến 127 và sai với hầu hết giá trị lớn hơn. Trước tiên, hãy chuyển chúng vềint. - Trả về một số cho
pop. Với định dạng này,poptrả về"null", giống nhưpush.
Câu hỏi thường gặp3
Làm thế nào để tìm giá trị nhỏ nhất của một ngăn xếp trong thời gian O(1)?
Hãy giữ một ngăn xếp thứ hai bên cạnh các giá trị để ghi lại giá trị nhỏ nhất ở mỗi độ cao, hoặc chỉ ghi lại mỗi giá trị nhỏ nhất mới. Khi đó, getMin đọc giá trị trên cùng của ngăn xếp này, và mỗi thao tác thêm hoặc lấy phần tử đều cập nhật cả hai ngăn xếp trong O(1).
Có thể triển khai ngăn xếp tối thiểu với bộ nhớ bổ sung O(1) không?
Có, chỉ với một ngăn xếp và một biến min. Để đẩy x xuống dưới min, hãy lưu 2x - min, giá trị này nhỏ hơn x và đánh dấu phần tử đó, rồi đặt min = x. Khi lấy phần tử được đánh dấu s ra, hãy khôi phục giá trị nhỏ nhất cũ bằng 2 * min - s. Khi tiến gần đến giới hạn 32 bit, cần dùng giá trị 64 bit.
Độ phức tạp về thời gian và không gian của Min Stack là gì?
Mỗi thao tác đều có độ phức tạp O(1): push, pop, top và getMin chỉ đọc hoặc thay đổi phần tử trên cùng của một hoặc hai ngăn xếp. Độ phức tạp không gian là O(n) với n giá trị được lưu trữ. Lưu giá trị nhỏ nhất bên cạnh mỗi giá trị luôn cần 2n vị trí; chỉ lưu các giá trị nhỏ nhất mới cần từ n + 1 đến 2n vị trí.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def minStackOps(ops, args):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"] args = [4, 1, 7, 0, 0, 0, 0, 0]
Đầu ra mong đợi
["null", "null", "null", "1", "null", "1", "null", "4"]