设计并实现特殊的堆栈数据结构|添加空间优化版-yiteyi-C++库

问题: 设计一个数据结构SpecialStack，该结构支持所有堆栈操作，如push（）、pop（）、isEmpty（）、isFull（）和一个额外的操作getMin（），该操作应该从SpecialStack返回最小元素。SpecialStack的所有这些操作都必须是O（1）。要实现SpecialStack，您应该只使用标准堆栈数据结构，而不使用其他数据结构，如数组、列表、。等

null

例子：

Consider the following SpecialStack16  --> TOP15291918When getMin() is called it should return 15, which is the minimum element in the current stack. If we do pop two times on stack, the stack becomes29  --> TOP1918When getMin() is called, it should return 18 which is the minimum in the current stack.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

解决方案： 使用两个堆栈：一个存储实际堆栈元素，另一个作为辅助堆栈存储最小值。其思想是以这样一种方式执行push（）和pop（）操作，即辅助堆栈的顶部总是最小的。让我们看看push（）和pop（）操作是如何工作的。

Push（int x）//将元素x插入特殊堆栈 1）将x推到第一个堆栈（包含实际元素的堆栈） 2）将x与第二个堆栈（辅助堆栈）的顶部元素进行比较。让顶部元素为y。 …..a）如果x小于y，则将x推到辅助堆栈。 …..b）如果x大于y，则将y推到辅助堆栈。 int Pop（）//从特殊堆栈中移除一个元素并返回移除的元素 1）从辅助堆栈中弹出顶部元素。 2）从实际堆栈中弹出顶部元素并返回它。第1步是必要的，以确保辅助堆栈也为未来的操作而更新。 int getMin（）//返回特殊堆栈中的最小元素 1）返回辅助堆栈的顶部元素。

我们可以看到 以上所有操作都是O（1） . 让我们来看一个例子。假设两个堆栈最初都是空的，并且18、19、29、15和16被插入到SpecialStack中。

When we insert 18, both stacks change to following.Actual Stack18 <--- top     Auxiliary Stack18 <---- topWhen 19 is inserted, both stacks change to following.Actual Stack19 <--- top     18Auxiliary Stack18 <---- top18When 29 is inserted, both stacks change to following.Actual Stack29 <--- top     1918Auxiliary Stack18 <---- top1818When 15 is inserted, both stacks change to following.Actual Stack15 <--- top     2919 18Auxiliary Stack15 <---- top181818When 16 is inserted, both stacks change to following.Actual Stack16 <--- top     152919 18Auxiliary Stack15 <---- top15181818

下面是SpecialStack类的实现。在下面的实现中，SpecialStack继承自堆栈，并有一个堆栈对象闵作为一个辅助堆栈。

C++

                         #include <iostream>                       
                         #include <stdlib.h>                       
           
                         using                                     namespace                                     std;                       
           
                         /* A simple stack class with                       
                         basic stack functionalities */                       
                         class                                     Stack {                       
                         private                                     :                       
                                                 static                                     const                                     int                                     max = 100;                       
                                                 int                                     arr[max];                       
                                                 int                                     top;                       
           
                         public                                     :                       
                                                 Stack() { top = -1; }                       
                                                 bool                                     isEmpty();                       
                                                 bool                                     isFull();                       
                                                 int                                     pop();                       
                                                 void                                     push(                                     int                                     x);                       
                         };                       
           
                         /* Stack's member method to check                       
                         if the stack is empty */                       
                         bool                                     Stack::isEmpty()                       
                         {                       
                                                 if                                     (top == -1)                       
                                                 return                                     true                                     ;                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         /* Stack's member method to check                       
                         if the stack is full */                       
                         bool                                     Stack::isFull()                       
                         {                       
                                                 if                                     (top == max - 1)                       
                                                 return                                     true                                     ;                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         /* Stack's member method to remove                       
                         an element from it */                       
                         int                                     Stack::pop()                       
                         {                       
                                                 if                                     (isEmpty()) {                       
                                                 cout <<                                     "Stack Underflow"                                     ;                       
                                                 abort                                     ();                       
                                                 }                       
                                                 int                                     x = arr[top];                       
                                                 top--;                       
                                                 return                                     x;                       
                         }                       
           
                         /* Stack's member method to insert                       
                         an element to it */                       
                         void                                     Stack::push(                                     int                                     x)                       
                         {                       
                                                 if                                     (isFull()) {                       
                                                 cout <<                                     "Stack Overflow"                                     ;                       
                                                 abort                                     ();                       
                                                 }                       
                                                 top++;                       
                                                 arr[top] = x;                       
                         }                       
           
                         /* A class that supports all the stack                       
                         operations and one additional                       
                                                 operation getMin() that returns the                       
                         minimum element from stack at                       
                                                 any time.  This class inherits from                       
                         the stack class and uses an                       
                                                 auxiliary stack that holds minimum                       
                         elements */                       
                         class                                     SpecialStack :                                     public                                     Stack {                       
                                                 Stack min;                       
           
                         public                                     :                       
                                                 int                                     pop();                       
                                                 void                                     push(                                     int                                     x);                       
                                                 int                                     getMin();                       
                         };                       
           
                         /* SpecialStack's member method to insert                       
                                                 an element to it. This method                       
                                                 makes sure that the min stack is also                       
                         updated with appropriate minimum                       
                                                 values */                       
                         void                                     SpecialStack::push(                                     int                                     x)                       
                         {                       
                                                 if                                     (isEmpty() ==                                     true                                     ) {                       
                                                 Stack::push(x);                       
                                                 min.push(x);                       
                                                 }                       
                                                 else                                     {                       
                                                 Stack::push(x);                       
                                                 int                                     y = min.pop();                       
                                                 min.push(y);                       
                                                 if                                     (x < y)                       
                                                 min.push(x);                       
                                                 else                       
                                                 min.push(y);                       
                                                 }                       
                         }                       
           
                         /* SpecialStack's member method to                       
                         remove an element from it. This method                       
                                                 removes top element from min stack also. */                       
                         int                                     SpecialStack::pop()                       
                         {                       
                                                 int                                     x = Stack::pop();                       
                                                 min.pop();                       
                                                 return                                     x;                       
                         }                       
           
                         /* SpecialStack's member method to get                       
                                                 minimum element from it. */                       
                         int                                     SpecialStack::getMin()                       
                         {                       
                                                 int                                     x = min.pop();                       
                                                 min.push(x);                       
                                                 return                                     x;                       
                         }                       
           
                         /* Driver program to test SpecialStack                       
                                                 methods */                       
                         int                                     main()                       
                         {                       
                                                 SpecialStack s;                       
                                                 s.push(10);                       
                                                 s.push(20);                       
                                                 s.push(30);                       
                                                 cout << s.getMin() << endl;                       
                                                 s.push(5);                       
                                                 cout << s.getMin();                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation of SpecialStack                       
                         // Note : here we use Stack class for                       
                         // Stack implementation                       
           
                         import                                     java.util.Stack;                       
           
                         /* A class that supports all the                       
                         stack operations and one additional                       
                         operation getMin() that returns                       
                         the minimum element from stack at                       
                         any time. This class inherits from                       
                         the stack class and uses an                       
                         auxiliary stack that holds minimum                       
                                                 elements */                       
           
                         class                                     SpecialStack                                     extends                                     Stack<Integer> {                       
                                                 Stack<Integer> min =                                     new                                     Stack<>();                       
           
                                                 /* SpecialStack's member method to                       
                         insert an element to it. This method                       
                                                 makes sure that the min stack is                       
                         also updated with appropriate minimum                       
                                                 values */                       
                                                 void                                     push(                                     int                                     x)                       
                                                 {                       
                                                 if                                     (isEmpty() ==                                     true                                     ) {                       
                                                 super                                     .push(x);                       
                                                 min.push(x);                       
                                                 }                       
                                                 else                                     {                       
                                                 super                                     .push(x);                       
                                                 int                                     y = min.pop();                       
                                                 min.push(y);                       
                                                 if                                     (x < y)                       
                                                 min.push(x);                       
                                                 else                       
                                                 min.push(y);                       
                                                 }                       
                                                 }                       
           
                                                 /* SpecialStack's member method to                       
                         insert an element to it. This method                       
                                                 makes sure that the min stack is                       
                         also updated with appropriate minimum                       
                                                 values */                       
                                                 public                                     Integer pop()                       
                                                 {                       
                                                 int                                     x =                                     super                                     .pop();                       
                                                 min.pop();                       
                                                 return                                     x;                       
                                                 }                       
           
                                                 /* SpecialStack's member method to get                       
                         minimum element from it. */                       
                                                 int                                     getMin()                       
                                                 {                       
                                                 int                                     x = min.pop();                       
                                                 min.push(x);                       
                                                 return                                     x;                       
                                                 }                       
           
                                                 /* Driver program to test SpecialStack                       
                         methods */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 SpecialStack s =                                     new                                     SpecialStack();                       
                                                 s.push(                                     10                                     );                       
                                                 s.push(                                     20                                     );                       
                                                 s.push(                                     30                                     );                       
                                                 System.out.println(s.getMin());                       
                                                 s.push(                                     5                                     );                       
                                                 System.out.println(s.getMin());                       
                                                 }                       
                         }                       
                         // This code is contributed by Sumit Ghosh                       

Python3

                         # Python3 program for the                       
                         # above approach                       
                         # A simple stack class with                       
                         # basic stack functionalities                       
                         class                                     stack:                       
           
                                                 def                                     __init__(                                     self                                     ):                       
           
                                                 self                                     .array                                     =                                     []                       
                                                 self                                     .top                                     =                                     -                                     1                       
                                                 self                                     .                                     max                                     =                                     100                       
           
                                                 # Stack's member method to check                       
                                                 # if the stack is empty                       
                                                 def                                     isEmpty(                                     self                                     ):                       
           
                                                 if                                     self                                     .top                                     =                                     =                                     -                                     1                                     :                       
                                                 return                                     True                       
                                                 else                                     :                       
                                                 return                                     False                       
           
                                                 # Stack's member method to check                       
                                                 # if the stack is full                       
                                                 def                                     isFull(                                     self                                     ):                       
                                   
                                                 if                                     self                                     .top                                     =                                     =                                     self                                     .                                     max                                     -                                     1                                     :                       
                                                 return                                     True                       
                                                 else                                     :                       
                                                 return                                     False                       
           
                                                 # Stack's member method to                       
                                                 # insert an element to it                       
           
                                                 def                                     push(                                     self                                     , data):                       
           
                                                 if                                     self                                     .isFull():                       
                                                 print                                     (                                     'Stack OverFlow'                                     )                       
                                                 return                       
                                                 else                                     :                       
                                                 self                                     .top                                     +                                     =                                     1                       
                                                 self                                     .array.append(data)                       
           
                                                 # Stack's member method to                       
                                                 # remove an element from it                       
                                                 def                                     pop(                                     self                                     ):                       
           
                                                 if                                     self                                     .isEmpty():                       
                                                 print                                     (                                     'Stack UnderFlow'                                     )                       
                                                 return                       
                                                 else                                     :                       
                                                 self                                     .top                                     -                                     =                                     1                       
                                                 return                                     self                                     .array.pop()                       
           
                         # A class that supports all the stack                       
                         # operations and one additional                       
                         # operation getMin() that returns the                       
                         # minimum element from stack at                       
                         # any time.  This class inherits from                       
                         # the stack class and uses an                       
                         # auxiliary stack that holds                       
                         # minimum elements                       
                         class                                     SpecialStack(stack):                       
           
                                                 def                                     __init__(                                     self                                     ):                       
                                                 super                                     ().__init__()                       
                                                 self                                     .                                     Min                                     =                                     stack()                       
           
                                                 # SpecialStack's member method to                       
                                                 # insert an element to it. This method                       
                                                 # makes sure that the min stack is also                       
                                                 # updated with appropriate minimum                       
                                                 # values                       
                                                 def                                     push(                                     self                                     , x):                       
           
                                                 if                                     self                                     .isEmpty():                       
                                                 super                                     ().push(x)                       
                                                 self                                     .                                     Min                                     .push(x)                       
                                                 else                                     :                       
                                                 super                                     ().push(x)                       
                                                 y                                     =                                     self                                     .                                     Min                                     .pop()                       
                                                 self                                     .                                     Min                                     .push(y)                       
                                                 if                                     x <                                     =                                     y:                       
                                                 self                                     .                                     Min                                     .push(x)                       
                                                 else                                     :                       
                                                 self                                     .                                     Min                                     .push(y)                       
           
                                                 # SpecialStack's member method to                       
                                                 # remove an element from it. This                       
                                                 # method removes top element from                       
                                                 # min stack also.                       
                                                 def                                     pop(                                     self                                     ):                       
           
                                                 x                                     =                                     super                                     ().pop()                       
                                                 self                                     .                                     Min                                     .pop()                       
                                                 return                                     x                       
           
                                                 # SpecialStack's member method                       
                                                 # to get minimum element from it.                       
                                                 def                                     getmin(                                     self                                     ):                       
           
                                                 x                                     =                                     self                                     .                                     Min                                     .pop()                       
                                                 self                                     .                                     Min                                     .push(x)                       
                                                 return                                     x                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                   
                                                 s                                     =                                     SpecialStack()                       
                                                 s.push(                                     10                                     )                       
                                                 s.push(                                     20                                     )                       
                                                 s.push(                                     30                                     )                       
                                                 print                                     (s.getmin())                       
                                                 s.push(                                     5                                     )                       
                                                 print                                     (s.getmin())                       
           
                         # This code is contributed by rachitkatiyar99                       

输出

复杂性分析：

时间复杂性：
1. 对于插入操作：O（1） （因为在堆栈中插入“推送”需要恒定的时间）
2. 对于删除操作：O（1） （因为在堆栈中删除“pop”需要恒定的时间）
3. 对于“获取最小值”操作：O（1） （因为我们使用了一个辅助堆栈，它的顶部是最小元素）
辅助空间： O（n）。使用辅助堆栈存储值。

空间优化版 上述方法可以优化。我们可以限制辅助堆栈中元素的数量。只有当主堆栈的传入元素小于或等于辅助堆栈的顶部时，我们才能推送。类似地，在弹出过程中，如果弹出元素等于辅助堆栈的顶部，则移除辅助堆栈的顶部元素。下面是push（）和pop（）的修改实现。

C++

                         /* SpecialStack's member method to                       
                                                 insert an element to it. This method                       
                                                 makes sure that the min stack is                       
                                                 also updated with appropriate minimum                       
                                                 values */                       
                         void                                     SpecialStack::push(                                     int                                     x)                       
                         {                       
                                                 if                                     (isEmpty() ==                                     true                                     ) {                       
                                                 Stack::push(x);                       
                                                 min.push(x);                       
                                                 }                       
                                                 else                                     {                       
                                                 Stack::push(x);                       
                                                 int                                     y = min.pop();                       
                                                 min.push(y);                       
           
                                                 /* push only when the incoming element                       
                                                 of main stack is smaller                       
                                                 than or equal to top of auxiliary stack */                       
                                                 if                                     (x <= y)                       
                                                 min.push(x);                       
                                                 }                       
                         }                       
           
                         /* SpecialStack's member method to                       
                                                 remove an element from it. This method                       
                                                 removes top element from min stack also. */                       
                         int                                     SpecialStack::pop()                       
                         {                       
                                                 int                                     x = Stack::pop();                       
                                                 int                                     y = min.pop();                       
           
                                                 /* Push the popped element y back                       
                                                 only if it is not equal to x */                       
                                                 if                                     (y != x)                       
                                                 min.push(y);                       
           
                                                 return                                     x;                       
                         }                       

JAVA

                         /* SpecialStack's member method to                       
                         insert an element to it. This method                       
                         makes sure that the min stack is                       
                         also updated with appropriate minimum                       
                         values */                       
           
                         void                                     push(                                     int                                     x)                       
                         {                       
                                                 if                                     (isEmpty() ==                                     true                                     ) {                       
                                                 super                                     .push(x);                       
                                                 min.push(x);                       
                                                 }                       
                                                 else                                     {                       
                                                 super                                     .push(x);                       
                                                 int                                     y = min.pop();                       
                                                 min.push(y);                       
           
                                                 /* push only when the incoming                       
                                                 element of main stack is smaller                       
                                                 than or equal to top of auxiliary stack */                       
                                                 if                                     (x <= y)                       
                                                 min.push(x);                       
                                                 }                       
                         }                       
           
                         /* SpecialStack's member method to                       
                                                 remove an element from it. This method                       
                                                 removes top element from min stack also. */                       
                         public                                     Integer pop()                       
                         {                       
                                                 int                                     x =                                     super                                     .pop();                       
                                                 int                                     y = min.pop();                       
           
                                                 /* Push the popped element y back                       
                                                 only if it is not equal to x */                       
                                                 if                                     (y != x)                       
                                                 min.push(y);                       
                                                 return                                     x;                       
                         }                       
           
                         // This code is contributed by Sumit Ghosh                       

Python3

                         ''' SpecialStack's member method to                       
                         insert an element to it. This method                       
                         makes sure that the min stack is                       
                         also updated with appropriate minimum                       
                         values '''                       
           
                         def                                     push(x):                       
                                                 if                                     (isEmpty()                                     =                                     =                                     True                                     ):                       
                                                 super                                     .append(x);                       
                                                 min                                     .append(x);                       
                                   
                                                 else                                     :                       
                                                 super                                     .append(x);                       
                                                 y                                     =                                     min                                     .pop();                       
                                                 min                                     .append(y);                       
           
                                                 ''' push only when the incoming                       
                                                 element of main stack is smaller                       
                                                 than or equal to top of auxiliary stack '''                       
                                                 if                                     (x <                                     =                                     y):                       
                                                 min                                     .append(x);                       
                                   
           
           
                         ''' SpecialStack's member method to                       
                                                 remove an element from it. This method                       
                                                 removes top element from min stack also. '''                       
                         def                                     pop():                       
                                                 x                                     =                                     super                                     .pop();                       
                                                 y                                     =                                     min                                     .pop();                       
           
                                                 ''' Push the popped element y back                       
                                                 only if it is not equal to x '''                       
                                                 if                                     (y !                                     =                                     x):                       
                                                 min                                     .append(y);                       
                                                 return                                     x;                       
           
           
                         # This code contributed by umadevi9616                       

C#

                         /* SpecialStack's member method to                       
                         insert an element to it. This method                       
                         makes sure that the min stack is                       
                         also updated with appropriate minimum                       
                         values */                       
           
                         void                                     push(                                     int                                     x)                       
                         {                       
                                                 if                                     (min.Count==0) {                       
                                                 super.Push(x);                       
                                                 min.Push(x);                       
                                                 }                       
                                                 else                                     {                       
                                                 super.Push(x);                       
                                                 int                                     y = min.Pop();                       
                                                 min.Push(y);                       
           
                                                 /* push only when the incoming                       
                                                 element of main stack is smaller                       
                                                 than or equal to top of auxiliary stack */                       
                                                 if                                     (x <= y)                       
                                                 min.Push(x);                       
                                                 }                       
                         }                       
           
                         /* SpecialStack's member method to                       
                                                 remove an element from it. This method                       
                                                 removes top element from min stack also. */                       
                         public                                     int                                     pop()                       
                         {                       
                                                 int                                     x = super.Pop();                       
                                                 int                                     y = min.Pop();                       
           
                                                 /* Push the popped element y back                       
                                                 only if it is not equal to x */                       
                                                 if                                     (y != x)                       
                                                 min.Push(y);                       
                                                 return                                     x;                       
                         }                       
           
                         // This code is contributed by umadevi9616                       

Javascript

                         <script>                       
                         /* SpecialStack's member method to                       
                         insert an element to it. This method                       
                         makes sure that the min stack is                       
                         also updated with appropriate minimum                       
                         values */                       
           
                         function                                     push(x)                       
                         {                       
                                                 if                                     (isEmpty() ==                                     true                                     ) {                       
                                                 super                                     .push(x);                       
                                                 min.push(x);                       
                                                 }                       
                                                 else                                     {                       
                                                 super                                     .push(x);                       
                                                 var                                     y = min.pop();                       
                                                 min.push(y);                       
           
                                                 /* push only when the incoming                       
                                                 element of main stack is smaller                       
                                                 than or equal to top of auxiliary stack */                       
                                                 if                                     (x <= y)                       
                                                 min.push(x);                       
                                                 }                       
                         }                       
           
                         /* SpecialStack's member method to                       
                                                 remove an element from it. This method                       
                                                 removes top element from min stack also. */                       
                                                 function                                     pop()                       
                         {                       
                                                 var                                     x =                                     super                                     .pop();                       
                                                 var                                     y = min.pop();                       
           
                                                 /* Push the popped element y back                       
                                                 only if it is not equal to x */                       
                                                 if                                     (y != x)                       
                                                 min.push(y);                       
                                                 return                                     x;                       
                         }                       
           
                         // This code is contributed by umadevi9616                       
                         </script>                       

复杂性分析：

时间复杂性：
1. 对于插入操作：O（1） （因为在堆栈中插入“推送”需要恒定的时间）
2. 对于删除操作：O（1） （因为在堆栈中删除“pop”需要恒定的时间）
3. 对于“获取最小值”操作：O（1） （因为我们使用了一个辅助元素，它的顶部是最小元素）
辅助空间： O（n）。最坏情况下的复杂度与上述相同，但在其他情况下，由于忽略了重复，其占用的空间将略小于上述方法。

进一步优化了O（1）时间复杂度和O（1）空间复杂度解决方案： 上述方法可以进一步优化，并且解决方案可以在O（1）时间复杂度和O（1）空间复杂度下工作。其思想是将最小元素（直到当前插入）与所有元素一起存储，作为虚拟_值的提醒，并将实际元素存储为虚拟_值的倍数。例如，在将元素“e”推入堆栈时，将其存储为 （e*DUMMY_值+minFoundSoFar） ，这样我们就知道在插入“e”时堆栈中存在的最小值是多少。

要弹出实际值，只需返回e/DUMMY_值，并将新的最小值设置为 （minFoundSoFar%DUMMY_值） .

注意：如果我们试图在堆栈中插入虚拟_值，以下方法将失败，因此我们必须仔细选择虚拟_值。 假设以下元素正在堆栈中插入–3 2 6 1 8 5

D 是虚拟值。

s 是包装器堆栈

顶部是堆栈的顶部元素

min是插入/删除图元时的最小值

以下步骤显示了上述变量在任何时刻的当前状态——

s、推（3）；最小=3 //更新了最小值，因为这里的堆栈为空 s={3*d+3} 顶部=（3*d+3）/d=3

s、推（2）；最小=2 //将最小值更新为最小值>当前元素 s={3*d+3 -> 2*d+2} 顶部=（2*d+2）/d=2

s、推（6）；最小=2 s={3*d+3 -> 2*d+2 -> 6*d+2} 顶部=（6*d+2）/d=6

s、推（1）；最小=1 //将最小值更新为最小值>当前元素 s={3*d+3->2*d+2->6*d+2->1*d+1} 顶部=（1*d+1）/d=1

s、推（8）；最小=1 s={3*d+3 -> 2*d+2 -> 6*d+2 -> 1*d+1 -> 8*d+1} 顶部=（8*d+1）/d=8

s、推（5）；最小=1 s={3*d+3 -> 2*d+2 -> 6*d+2 -> 1*d+1 -> 8*d+1 -> 5*d+1} 顶部=（5*d+1）/d=5

s、 pop（）； s={3*d+3->2*d+2->6*d+2->1*d+1->8*d+1->5*d+1} 顶部=（5*d+1）/d=5 最小值=（8*d+1）%d=1 //min始终是堆栈中第二个顶部元素的剩余部分。

s、 pop（）； s={3*d+3->2*d+2->6*d+2->1*d+1->8*d+1} 顶部=（8*d+1）/d=8 最小值=（1*d+1）%d=1

s、 pop（） s={3*d+3->2*d+2->6*d+2->1*d+1} 顶部=（1*d+1）/d=1 最小值=（6*d+2）%d=2

s、 pop（） s={3*d+3->2*d+2->6*d+2} 顶部=（6*d+2）/d=6 最小值=（2*d+2）%d=2

s、 pop（） s={3*d+3->2*d+2} 顶部=（2*d+2）/d=2 最小值=（3*d+3）%d=3

s、 pop（） s={3*d+3} 顶部=（3*d+3）/d=3 min=-1//因为堆栈现在是空的

C++

                         #include <iostream>                       
                         #include <stack>                       
                         #include <vector>                       
                         using                                     namespace                                     std;                       
           
                         /* A special stack having peek() pop() and                       
                                                 * push() along with additional getMin() that                       
                                                 * returns minimum value in a stack without                       
                                                 * using extra space and all operations in O(1)                       
                                                 * time.. ???? */                       
                         class                                     SpecialStack                       
                         {                       
                                   
                                                 // Sentinel value for min                       
                                                 int                                     min = -1;                       
                                   
                                                 // DEMO_VALUE                       
                                                 static                                     const                                     int                                     demoVal = 9999;                       
                                                 stack<                                     int                                     > st;                       
           
                         public                                     :                       
           
                                                 void                                     getMin()                       
                                                 {                       
                                                 cout <<                                     "min is: "                                     << min << endl;                       
                                                 }                       
           
                                                 void                                     push(                                     int                                     val)                       
                                                 {                       
                                   
                                                 // If stack is empty OR current element                       
                                                 // is less than min, update min.                       
                                                 if                                     (st.empty() || val < min)                       
                                                 {                       
                                                 min = val;                       
                                                 }                       
                                   
                                                 // Encode the current value with                       
                                                 // demoVal, combine with min and                       
                                                 // insert into stack                       
                                                 st.push(val * demoVal + min);                       
                                                 cout <<                                     "pushed: "                                     << val << endl;                       
                                                 }                       
           
                                                 int                                     pop()                       
                                                 {                       
                                                 // if stack is empty return -1;                       
                                                 if                                     ( st.empty() ) {                       
                                                 cout <<                                     "stack underflow"                                     << endl ;                       
                                                 return                                     -1;                       
                                                 }                       
                                   
                                                 int                                     val = st.top();                       
                                                 st.pop();                       
                                   
                                                 // If stack is empty, there would                       
                                                 // be no min value present, so                       
                                                 // make min as -1                       
                                                 if                                     (!st.empty())                       
                                                 min = st.top() % demoVal;                       
                                                 else                       
                                                 min = -1;                       
                                   
                                                 cout <<                                     "popped: "                                     << val / demoVal << endl;                       
                                   
                                                 // Decode actual value from                       
                                                 // encoded value                       
                                                 return                                     val / demoVal;                       
                                                 }                       
           
                                                 int                                     peek()                       
                                                 {                       
                                   
                                                 // Decode actual value                       
                                                 // from encoded value                       
                                                 return                                     st.top() / demoVal;                       
                                                 }                       
                         };                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 SpecialStack s;                       
           
                                                 vector<                                     int                                     > arr = { 3, 2, 6, 1, 8, 5, 5, 5, 5 };                       
           
                                                 for                                     (                                     int                                     i = 0; i < arr.size(); i++)                       
                                                 {                       
                                                 s.push(arr[i]);                       
                                                 s.getMin();                       
                                                 }                       
                                   
                                                 cout << endl;                       
                                                 for                                     (                                     int                                     i = 0; i < arr.size(); i++)                       
                                                 {                       
                                                 s.pop();                       
                                                 s.getMin();                       
                                                 }                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by scisaif                       

JAVA

                         import                                     java.util.Stack;                       
           
                         /* A special stack having peek() pop() and push() along with                       
                                                 * additional getMin() that returns minimum value in a stack                       
                                                 * without using extra space and all operations in O(1)                       
                                                 * time.. :slightly_smiling_face:                       
                                                 * */                       
                         public                                     class                                     SpecialStack {                       
           
                                                 int                                     min = -                                     1                                     ;                                     // sentinel value for min                       
                                                 static                                     int                                     demoVal =                                     9999                                     ;                                     // DEMO_VALUE                       
                                                 Stack<Integer> st =                                     new                                     Stack<Integer>();                       
           
                                                 void                                     getMin() { System.out.println(                                     "min is: "                                     + min); }                       
           
                                                 void                                     push(                                     int                                     val)                       
                                                 {                       
                                                 // if stack is empty OR current element is less than                       
                                                 // min, update min..                       
                                                 if                                     (st.isEmpty() || val < min) {                       
                                                 min = val;                       
                                                 }                       
           
                                                 st.push(val * demoVal                       
                                                 + min);                                     // encode the current value with                       
                                                 // demoVal, combine with min and                       
                                                 // insert into stack                       
                                                 System.out.println(                                     "pushed: "                                     + val);                       
                                                 }                       
           
                                                 int                                     pop()                       
                                                 {                       
                                                 // if stack is empty return -1;                       
                                                 if                                     (st.isEmpty() ) {                       
                                                 System.out.println(                                     "stack underflow"                                     );                       
                                                 return                                     -                                     1                                     ;                       
                                                 }                       
                                   
                                                 int                                     val = st.pop();                       
           
                                                 if                                     (!st.isEmpty())                                     // if stack is empty, there would                       
                                                 // be no min value present, so                       
                                                 // make min as -1                       
                                                 min = st.peek() % demoVal;                       
                                                 else                       
                                                 min = -                                     1                                     ;                       
                                                 System.out.println(                                     "popped: "                                     + val / demoVal);                       
                                                 return                                     val / demoVal;                                     // decode actual value from                       
                                                 // encoded value                       
                                                 }                       
           
                                                 int                                     peek()                       
                                                 {                       
                                                 return                                     st.peek() / demoVal;                                     // decode actual value                       
                                                 // from encoded value                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 SpecialStack s =                                     new                                     SpecialStack();                       
           
                                                 int                                     [] arr = {                                     3                                     ,                                     2                                     ,                                     6                                     ,                                     1                                     ,                                     8                                     ,                                     5                                     ,                                     5                                     ,                                     5                                     ,                                     5                                     };                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < arr.length; i++) {                       
                                                 s.push(arr[i]);                       
                                                 s.getMin();                       
                                                 }                       
                                                 System.out.println();                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < arr.length; i++) {                       
                                                 s.pop();                       
                                                 s.getMin();                       
                                                 }                       
                                                 }                       
                         }                       

C#

                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
           
                         /* A special stack having peek() pop() and push() along with                       
                                                 * additional getMin() that returns minimum value in a stack                       
                                                 * without using extra space and all operations in O(1)                       
                                                 * time.. :slightly_smiling_face:                       
                                                 * */                       
                         public                                     class                                     SpecialStack {                       
           
                                                 int                                     min = -1;                                     // sentinel value for min                       
                                                 static                                     int                                     demoVal = 9999;                                     // DEMO_VALUE                       
                                                 Stack<                                     int                                     > st =                                     new                                     Stack<                                     int                                     >();                       
           
                                                 void                                     getMin() { Console.WriteLine(                                     "min is: "                                     + min); }                       
           
                                                 void                                     push(                                     int                                     val)                       
                                                 {                       
                                                 // if stack is empty OR current element is less than                       
                                                 // min, update min..                       
                                                 if                                     (st.Count==0 || val < min) {                       
                                                 min = val;                       
                                                 }                       
           
                                                 st.Push(val * demoVal                       
                                                 + min);                                     // encode the current value with                       
                                                 // demoVal, combine with min and                       
                                                 // insert into stack                       
                                                 Console.WriteLine(                                     "pushed: "                                     + val);                       
                                                 }                       
           
                                                 int                                     pop()                       
                                                 {                       
                                                 // if stack is empty return -1;                       
                                                 if                                     (st.Count==0 ) {                       
                                                 Console.WriteLine(                                     "stack underflow"                                     );                       
                                                 return                                     -1;                       
                                                 }                       
                                   
                                                 int                                     val = st.Pop();                       
           
                                                 if                                     (st.Count!=0)                                     // if stack is empty, there would                       
                                                 // be no min value present, so                       
                                                 // make min as -1                       
                                                 min = st.Peek() % demoVal;                       
                                                 else                       
                                                 min = -1;                       
                                                 Console.WriteLine(                                     "popped: "                                     + val / demoVal);                       
                                                 return                                     val / demoVal;                                     // decode actual value from                       
                                                 // encoded value                       
                                                 }                       
           
                                                 int                                     peek()                       
                                                 {                       
                                                 return                                     st.Peek() / demoVal;                                     // decode actual value                       
                                                 // from encoded value                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 SpecialStack s =                                     new                                     SpecialStack();                       
           
                                                 int                                     [] arr = { 3, 2, 6, 1, 8, 5, 5, 5, 5 };                       
           
                                                 for                                     (                                     int                                     i = 0; i < arr.Length; i++) {                       
                                                 s.push(arr[i]);                       
                                                 s.getMin();                       
                                                 }                       
                                                 Console.WriteLine();                       
                                                 for                                     (                                     int                                     i = 0; i < arr.Length; i++) {                       
                                                 s.pop();                       
                                                 s.getMin();                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // This code is contributed by gauravrajput1                       

输出

pushed: 3min is: 3pushed: 2min is: 2pushed: 6min is: 2pushed: 1min is: 1pushed: 8min is: 1pushed: 5min is: 1pushed: 5min is: 1pushed: 5min is: 1pushed: 5min is: 1popped: 5min is: 1popped: 5min is: 1popped: 5min is: 1popped: 5min is: 1popped: 8min is: 1popped: 1min is: 2popped: 6min is: 2popped: 2min is: 3popped: 3min is: -1

复杂性分析：

对于push（）操作： O（1）（因为在堆栈中插入“推送”需要恒定的时间） 对于pop（）操作： O（1）（因为堆栈中的pop操作需要恒定的时间）

对于“Get Min”操作： O（1）（在整个代码中，我们一直保持最小变量）

辅助空间： O（1）。没有额外的空间被使用。

https://youtu.be/1Ld7gbW1oHc 设计一个在O（1）时间和O（1）额外空间内支持getMin（）的堆栈 幸亏 @文基 , @斯瓦鲁普和 @黄晶感谢他们的投入。如果你发现上面的代码不正确，请写评论，或者寻找其他方法来解决同样的问题。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章