这是一道面试题。
您需要设计一个存储整数值的栈，使得
getMinimum()函数返回栈中的最小元素。例如：
案例 #1
5 ← 栈顶
1
4
6
2当调用
getMinimum()时，应该返回 1，即栈中的最小元素。案例 #2
stack.pop()
stack.pop()注意：5 和 1 都已经弹出了栈。 弹出后，栈看起来像这样:
4 ← 栈顶
6
2当调用
getMinimum()时，应该返回 2，这是栈中的最小元素。约束条件:
getMinimum函数的时间复杂度应为 O(1)- 在设计时还必须考虑空间限制，并且如果使用额外的空间，则应为常量空间。
编辑：这不符合“常数空间”约束条件-它基本上会使所需的空间加倍。但我非常怀疑，如果没有在某个地方破坏运行时复杂性（例如使push/pop O(n)），就不会有解决方案。请注意，这并不改变所需空间的复杂度，例如，如果您有一个具有O(n)空间要求的堆栈，则仍将是O(n)，只是具有不同的常数因子。
非常数空间解决方案
保留一个“重复”的堆栈，其中包含“堆栈中所有较低值的最小值”。当您弹出主堆栈时，请同时弹出min堆栈。当您推入主堆栈时，请推入新元素或当前最小值中的较低者。getMinimum()实现为minStack.peek()。
因此，使用您的示例，我们将拥有：
Real stack Min stack
5 --> TOP 1
1 1
4 2
6 2
2 2
弹出两次后，您将得到：
Real stack Min stack
4 2
6 2
2 2
如果这不够详细，请告诉我。一旦你理解了，它就很简单了，但一开始可能需要一点思考:)
当然，缺点是它会使空间需求加倍。执行时间并没有显著的影响，即复杂度仍然相同。
编辑：有一个稍微棘手一些但通常具有更好的空间的变体。我们仍然有最小堆栈，但只有在从主堆栈弹出的值等于最小堆栈上的值时才从中弹出。只有在将要推到主堆栈的值小于或等于当前最小值时，我们才将其推到最小堆栈上。这允许重复的最小值。getMinimum()仍然只是一个查看操作。例如，对原始版本再次推入1，我们将得到：
Real stack Min stack
1 --> TOP 1
5 1
1 2
4
6
2
Real stack Min stack
5 --> TOP 1
1 2
4
6
2
Real stack Min stack
1 1
4 2
6
2
Real stack Min stack
4 2
6
2
using System.Collections.Generic;
public class FastMinStack<T>
{
private readonly Stack<T> stack = new Stack<T>();
// Could pass this in to the constructor
private readonly IComparer<T> comparer = Comparer<T>.Default;
private T currentMin;
public T Minimum
{
get { return currentMin; }
}
public void Push(T element)
{
if (stack.Count == 0 ||
comparer.Compare(element, currentMin) <= 0)
{
stack.Push(currentMin);
stack.Push(element);
currentMin = element;
}
else
{
stack.Push(element);
}
}
public T Pop()
{
T ret = stack.Pop();
if (comparer.Compare(ret, currentMin) == 0)
{
currentMin = stack.Pop();
}
return ret;
}
}
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; } }
}
Stack.min() 来获取 Stack.pop() 后的最小值。但是 Stack.min() 的时间复杂度是多少？它是否会在内部扫描整个 Stack 来获取最小元素？ - SkrewEverythingpublic class StackWithMin {
int min;
int size;
int[] data = new int[1024];
public void push ( int val ) {
if ( size == 0 ) {
data[size] = val;
min = val;
} else if ( val < min) {
data[size] = 2 * val - min;
min = val;
assert (data[size] < min);
} else {
data[size] = val;
}
++size;
// check size and grow array
}
public int getMin () {
return min;
}
public int pop () {
--size;
int val = data[size];
if ( ( size > 0 ) && ( val < min ) ) {
int prevMin = min;
min += min - val;
return prevMin;
} else {
return val;
}
}
public boolean isEmpty () {
return size == 0;
}
public static void main (String...args) {
StackWithMin stack = new StackWithMin();
for ( String arg: args )
stack.push( Integer.parseInt( arg ) );
while ( ! stack.isEmpty() ) {
int min = stack.getMin();
int val = stack.pop();
System.out.println( val + " " + min );
}
System.out.println();
}
}
它显式地存储当前的最小值，如果最小值发生变化，则不会将该值推入栈中，而是推入一个相同差异的值到新最小值的另一侧（例如，如果min = 7并且您push 5，则会推入3而不是5-|7-5|=3），然后将min设置为5；如果在min为5时弹出3，则它会看到弹出的值小于min，所以逆转过程以获得7作为新的最小值，然后返回先前的min。由于任何不改变当前最小值的值都大于当前最小值，因此可以用它来区分改变最小值和不改变最小值的值。
在使用固定大小整数的语言中，你从值的表示中借用了一点空间，因此可能会下溢并导致assert失败。但是除此之外，它是恒定的额外空间，所有操作仍然是O（1）。
基于链表的堆栈有其他可以借用的地方，例如在C中使用next指针的最低有效位，在Java中使用链接列表中对象的类型。对于Java来说，这意味着与连续堆栈相比使用了更多的空间，因为每个链接都有对象开销：
public class LinkedStackWithMin {
private static class Link {
final int value;
final Link next;
Link ( int value, Link next ) {
this.value = value;
this.next = next;
}
int pop ( LinkedStackWithMin stack ) {
stack.top = next;
return value;
}
}
private static class MinLink extends Link {
MinLink ( int value, Link next ) {
super( value, next );
}
int pop ( LinkedStackWithMin stack ) {
stack.top = next;
int prevMin = stack.min;
stack.min = value;
return prevMin;
}
}
Link top;
int min;
public LinkedStackWithMin () {
}
public void push ( int val ) {
if ( ( top == null ) || ( val < min ) ) {
top = new MinLink(min, top);
min = val;
} else {
top = new Link(val, top);
}
}
public int pop () {
return top.pop(this);
}
public int getMin () {
return min;
}
public boolean isEmpty () {
return top == null;
}
C语言中并不存在这样的开销，而且您可以借用下一个指针的最低位：
typedef struct _stack_link stack_with_min;
typedef struct _stack_link stack_link;
struct _stack_link {
size_t next;
int value;
};
stack_link* get_next ( stack_link* link )
{
return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
}
bool is_min ( stack_link* link )
{
return ( link -> next & 1 ) ! = 0;
}
void push ( stack_with_min* stack, int value )
{
stack_link *link = malloc ( sizeof( stack_link ) );
link -> next = ( size_t ) stack -> next;
if ( (stack -> next == 0) || ( value == stack -> value ) ) {
link -> value = stack -> value;
link -> next |= 1; // mark as min
} else {
link -> value = value;
}
stack -> next = link;
}
etc.;
然而，这些算法都不是真正的O(1)。它们在实践中不需要更多的空间，因为它们利用了这些语言中数字、对象或指针表示中的空洞。但是，一个使用更紧凑表示的理论机器在每种情况下都需要添加一个额外的比特位到该表示中。
Integer.MIN_VALUE（例如：push 1，push Integer.MIN_VALUE，pop），则会产生错误的pop()结果。这是由于上面提到的下溢。否则，对于所有整数值都有效。 - Theo我找到了一种解决方案，它满足所有提到的限制（常数时间操作）和常数额外空间。
思路是存储最小值与输入数字之间的差异，并在不再是最小值时更新最小值。
代码如下：
public class MinStack {
long min;
Stack<Long> stack;
public MinStack(){
stack = new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()) {
stack.push(0L);
min = x;
} else {
stack.push(x - min); //Could be negative if min value needs to change
if (x < min) min = x;
}
}
public int pop() {
if (stack.isEmpty()) return;
long pop = stack.pop();
if (pop < 0) {
long ret = min
min = min - pop; //If negative, increase the min value
return (int)ret;
}
return (int)(pop + min);
}
public int top() {
long top = stack.peek();
if (top < 0) {
return (int)min;
} else {
return (int)(top + min);
}
}
public int getMin() {
return (int)min;
}
}
该解法来自：https://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack
那么，push和pop的运行时间限制是什么？如果它们不需要是常数级别的，则只需计算这两个操作中的最小值（使它们为O（n））。否则，我看不出如何使用恒定的额外空间来完成此操作。
假设我们要处理的堆栈是这样的：
最初的回答：
6 , minvalue=2
2 , minvalue=2
5 , minvalue=3
3 , minvalue=3
9 , minvalue=7
7 , minvalue=7
8 , minvalue=8
6 , minvalue=2
y1 , minvalue=2
5 , minvalue=3
y2 , minvalue=3
9 , minvalue=7
y3 , minvalue=7
8 , minvalue=8
Let's do the math:
x < prevMinvalue [Given]
x - prevMinvalue < 0
x - prevMinValue + x < 0 + x [Add x on both side]
2*x - prevMinValue < x
this is the y which we were looking for less than x(newMinValue).
y = 2*x - prevMinValue. 'or' y = 2*newMinValue - prevMinValue 'or' y = 2*curMinValue - prevMinValue [taking curMinValue=newMinValue].
如果在推入x的时候它小于prevMinValue，那么我们就推入y[2*x-prevMinValue]并更新newMinValue = x。
而当弹出时，如果栈中包含小于minValue的元素，那么这就是我们更新minValue的时机。我们需要从curMinValue和y计算prevMinValue。
y = 2*curMinValue - prevMinValue [已证明]
prevMinValue = 2*curMinvalue - y。
2*curMinValue - y 是我们现在需要更新为prevMinValue的数字。
以下是采用相同逻辑的代码，时间复杂度为O(1)，空间复杂度为O(1)。
// C++ program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
// A user defined stack that supports getMin() in
// addition to push() and pop()
struct MyStack
{
stack<int> s;
int minEle;
// Prints minimum element of MyStack
void getMin()
{
if (s.empty())
cout << "Stack is empty\n";
// variable minEle stores the minimum element
// in the stack.
else
cout <<"Minimum Element in the stack is: "
<< minEle << "\n";
}
// Prints top element of MyStack
void peek()
{
if (s.empty())
{
cout << "Stack is empty ";
return;
}
int t = s.top(); // Top element.
cout << "Top Most Element is: ";
// If t < minEle means minEle stores
// value of t.
(t < minEle)? cout << minEle: cout << t;
}
// Remove the top element from MyStack
void pop()
{
if (s.empty())
{
cout << "Stack is empty\n";
return;
}
cout << "Top Most Element Removed: ";
int t = s.top();
s.pop();
// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
cout << minEle << "\n";
minEle = 2*minEle - t;
}
else
cout << t << "\n";
}
// Removes top element from MyStack
void push(int x)
{
// Insert new number into the stack
if (s.empty())
{
minEle = x;
s.push(x);
cout << "Number Inserted: " << x << "\n";
return;
}
// If new number is less than minEle
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
else
s.push(x);
cout << "Number Inserted: " << x << "\n";
}
};
// Driver Code
int main()
{
MyStack s;
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
return 0;
}
class MinStackOptimized:
def __init__(self):
self.stack = []
self.min = None
def push(self, x):
if not self.stack:
# stack is empty therefore directly add
self.stack.append(x)
self.min = x
else:
"""
Directly add (x-self.min) to the stack. This also ensures anytime we have a
negative number on the stack is when x was less than existing minimum
recorded thus far.
"""
self.stack.append(x-self.min)
if x < self.min:
# Update x to new min
self.min = x
def pop(self):
x = self.stack.pop()
if x < 0:
"""
if popped element was negative therefore this was the minimum
element, whose actual value is in self.min but stored value is what
contributes to get the next min. (this is one of the trick we use to ensure
we are able to get old minimum once current minimum gets popped proof is given
below in pop method), value stored during push was:
(x - self.old_min) and self.min = x therefore we need to backtrack
these steps self.min(current) - stack_value(x) actually implies to
x (self.min) - (x - self.old_min)
which therefore gives old_min back and therefore can now be set
back as current self.min.
"""
self.min = self.min - x
def top(self):
x = self.stack[-1]
if x < 0:
"""
As discussed above anytime there is a negative value on stack, this
is the min value so far and therefore actual value is in self.min,
current stack value is just for getting the next min at the time
this gets popped.
"""
return self.min
else:
"""
if top element of the stack was positive then it's simple, it was
not the minimum at the time of pushing it and therefore what we did
was x(actual) - self.min(min element at current stage) let's say `y`
therefore we just need to reverse the process to get the actual
value. Therefore self.min + y, which would translate to
self.min + x(actual) - self.min, thereby giving x(actual) back
as desired.
"""
return x + self.min
def getMin(self):
# Always self.min variable holds the minimum so for so easy peezy.
return self.min
class Node:
def __init__(self, value):
self.value = value
self.next = None
class MinStack:
def __init__(self):
self.head = None
self.min = float('inf')
# @param x, an integer
def push(self, x):
if self.head == None:
self.head = Node(x)
self.min = x
else:
if x >= self.min:
n = Node(x)
n.next = self.head
self.head = n
else:
v = 2 * x - self.min
n = Node(v)
n.next = self.head
self.head = n
self.min = x
# @return nothing
def pop(self):
if self.head:
if self.head.value < self.min:
self.min = self.min * 2 - self.head.value
self.head = self.head.next
# @return an integer
def top(self):
if self.head:
if self.head.value < self.min:
self.min = self.min * 2 - self.head.value
return self.min
else:
return self.head.value
else:
return -1
# @return an integer
def getMin(self):
if self.head:
return self.min
else:
return -1
从栈中获取最小元素。我们必须使用两个栈，即栈s1和栈s2。
---------------------递归调用步骤2到4-----------------------
如果向栈s1添加新元素，则从栈s2中弹出元素
将新元素与s2进行比较。哪一个更小，就推入s2。
从包含最小元素的栈s2中弹出
代码如下：
package Stack;
import java.util.Stack;
public class getMin
{
Stack<Integer> s1= new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
void push(int x)
{
if(s1.isEmpty() || s2.isEmpty())
{
s1.push(x);
s2.push(x);
}
else
{
s1. push(x);
int y = (Integer) s2.pop();
s2.push(y);
if(x < y)
s2.push(x);
}
}
public Integer pop()
{
int x;
x=(Integer) s1.pop();
s2.pop();
return x;
}
public int getmin()
{
int x1;
x1= (Integer)s2.pop();
s2.push(x1);
return x1;
}
public static void main(String[] args) {
getMin s = new getMin();
s.push(10);
s.push(20);
s.push(30);
System.out.println(s.getmin());
s.push(1);
System.out.println(s.getmin());
}
}
这是我使用链表的Java解决方案。
class Stack{
int min;
Node top;
static class Node{
private int data;
private Node next;
private int min;
Node(int data, int min){
this.data = data;
this.min = min;
this.next = null;
}
}
void push(int data){
Node temp;
if(top == null){
temp = new Node(data,data);
top = temp;
top.min = data;
}
if(top.min > data){
temp = new Node(data,data);
temp.next = top;
top = temp;
} else {
temp = new Node(data, top.min);
temp.next = top;
top = temp;
}
}
void pop(){
if(top != null){
top = top.next;
}
}
int min(){
return top.min;
}
}