這是面試問題之一。您需要設(shè)計一個包含整數(shù)值的堆棧，以便getMinimum（）函數(shù)應(yīng)返回堆棧中的最小元素。例如：考慮以下示例情況15->頂部1個462調(diào)用getMinimum（）時，它應(yīng)返回1，這是最小元素 在堆棧中。 情況＃2stack.pop（）stack.pop（）注意：5和1都從堆棧中彈出。所以之后，堆棧看起來像，4->頂部62調(diào)用getMinimum（）時應(yīng)返回2，這是 堆。食用者：getMinimum應(yīng)該返回O（1）中的最小值設(shè)計時還必須考慮空間約束，如果您使用額外的空間，則它應(yīng)該具有恒定的空間。
3 回答
慕勒3428872
TA貢獻(xiàn)1848條經(jīng)驗 獲得超6個贊
添加一個字段以保存最小值，并在Pop（）和Push（）期間對其進(jìn)行更新。這樣，getMinimum（）將為O（1），但是Pop（）和Push（）將不得不做更多的工作。
如果彈出最小值，則Pop（）將為O（n），否則它們?nèi)詫⒕鶠镺（1）。調(diào)整大小時，根據(jù)Stack實現(xiàn)，Push（）變?yōu)镺（n）。
這是一個快速實施
public sealed class MinStack {
private int MinimumValue;
private readonly Stack<int> Stack = new Stack<int>();
public int GetMinimum() {
if (IsEmpty) {
throw new InvalidOperationException("Stack is empty");
}
return MinimumValue;
}
public int Pop() {
var value = Stack.Pop();
if (value == MinimumValue) {
MinimumValue = Stack.Min();
}
return value;
}
public void Push(int value) {
if (IsEmpty || value < MinimumValue) {
MinimumValue = value;
}
Stack.Push(value);
}
private bool IsEmpty { get { return Stack.Count() == 0; } }
}
添加回答
舉報
0/150
提交
取消