這是面試問題之一。您需要設計一個包含整數值的堆棧，以便getMinimum（）函數應返回堆棧中的最小元素。例如：考慮以下示例情況15->頂部1個462調用getMinimum（）時，它應返回1，這是最小元素 在堆棧中。 情況＃2stack.pop（）stack.pop（）注意：5和1都從堆棧中彈出。所以之后，堆?？雌饋硐?，4->頂部62調用getMinimum（）時應返回2，這是 堆。食用者：getMinimum應該返回O（1）中的最小值設計時還必須考慮空間約束，如果您使用額外的空間，則它應該具有恒定的空間。
3 回答
慕勒3428872
TA貢獻1848條經驗 獲得超6個贊
添加一個字段以保存最小值，并在Pop（）和Push（）期間對其進行更新。這樣，getMinimum（）將為O（1），但是Pop（）和Push（）將不得不做更多的工作。
如果彈出最小值，則Pop（）將為O（n），否則它們仍將均為O（1）。調整大小時，根據Stack實現，Push（）變為O（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
提交
取消