问题: 设计一个数据结构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.
讨论了一种使用O（1）时间和O（n）额外空间的方法 在这里 . 在本文中，讨论了一种新的方法，该方法支持带有O（1）额外空间的极小值。我们定义一个变量 米内尔 在堆栈中存储当前最小元素的。现在有趣的部分是，当最小元素被移除时，如何处理这种情况。为了处理这个问题，我们将“2x–minEle”推到堆栈中，而不是x，这样就可以使用当前minEle及其存储在堆栈中的值来检索之前的最小元素。以下是工作的详细步骤和说明。 推（x） ：在堆栈顶部插入x。
- 如果堆栈为空，则在堆栈中插入x，并使minEle等于x。
- 如果堆栈不是空的，请将x与minEle进行比较。出现两种情况：
- 如果x大于或等于minEle，只需插入x即可。
- 如果x小于minEle，则将（2*x–minEle）插入堆栈，并使minEle等于x。例如，让前一个minEle为3。现在我们要插入2。我们将minEle更新为2，并在堆栈中插入2*2–3=1。
Pop（）： 从堆栈顶部移除元素。
- 从顶部拆下滤芯。将移除的元素设为y。出现两种情况：
- 如果y大于或等于minEle，堆栈中的最小元素仍然是minEle。
- 如果y小于minEle，最小元素现在变为（2*minEle–y），所以更新（minEle=2*minEle–y）。这是我们从当前最小值中检索前一个最小值及其在堆栈中的值的地方。例如，要删除的元素为1，minEle为2。我们删除1并将minEle更新为2*2–1=3。
要点：
- 如果元素的实际值是目前为止的最小值，则堆栈不会保存该元素的实际值。
- 实际最小元素始终存储在minEle中
插图
推（x）
- 要插入的数字：3，堆栈为空，所以在堆栈中插入3，minEle=3。
- 要插入的数字：5，堆栈不为空，5>minEle，将5插入堆栈，minEle=3。
- 要插入的编号：2，堆栈不为空，2
- 要插入的数字：1，堆栈不为空，1
- 要插入的数字：1，堆栈不为空，1=minEle，在堆栈中插入1，minEle=1。
- 要插入的数字：-1，堆栈不是空的，-1
- 要插入的数字：1，堆栈不为空，1
Pop（）
- 最初，堆栈中的最小元素minEle为-1。
- 删除的数字：-3，因为-3小于最小元素，所以要删除的原始数字是minEle，即-1，新的minEle=2*-1-（-3）=1
- 移除的数字：1，1==minEle，所以移除的数字是1，minEle仍然等于1。
- 删除的数字：0，0
- 删除的编号：1，1
- 删除的数字：5，5>minEle，原来的数字是5，minEle仍然是3
- 删除的编号：1，1
C++
// 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" ; // variable minEle stores the minimum element // in the stack. else cout << "Minimum Element in the stack is: " << minEle << "" ; } // 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" ; 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 << "" ; minEle = 2*minEle - t; } else cout << t << "" ; } // 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 << "" ; return ; } // If new number is less than minEle else if (x < minEle) { s.push(2*x - minEle); minEle = x; } else s.push(x); cout << "Number Inserted: " << x << "" ; } }; // 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; } |
JAVA
// Java program to implement a stack that supports // getMinimum() in O(1) time and O(1) extra space. import java.util.*; // A user defined stack that supports getMin() in // addition to push() and pop() class MyStack { Stack<Integer> s; Integer minEle; // Constructor MyStack() { s = new Stack<Integer>(); } // Prints minimum element of MyStack void getMin() { // Get the minimum number in the entire stack if (s.isEmpty()) System.out.println( "Stack is empty" ); // variable minEle stores the minimum element // in the stack. else System.out.println( "Minimum Element in the " + " stack is: " + minEle); } // prints top element of MyStack void peek() { if (s.isEmpty()) { System.out.println( "Stack is empty " ); return ; } Integer t = s.peek(); // Top element. System.out.print( "Top Most Element is: " ); // If t < minEle means minEle stores // value of t. if (t < minEle) System.out.println(minEle); else System.out.println(t); } // Removes the top element from MyStack void pop() { if (s.isEmpty()) { System.out.println( "Stack is empty" ); return ; } System.out.print( "Top Most Element Removed: " ); Integer t = s.pop(); // Minimum will change as the minimum element // of the stack is being removed. if (t < minEle) { System.out.println(minEle); minEle = 2 *minEle - t; } else System.out.println(t); } // Insert new number into MyStack void push(Integer x) { if (s.isEmpty()) { minEle = x; s.push(x); System.out.println( "Number Inserted: " + x); return ; } // If new number is less than original minEle if (x < minEle) { s.push( 2 *x - minEle); minEle = x; } else s.push(x); System.out.println( "Number Inserted: " + x); } }; // Driver Code public class Main { public static void main(String[] args) { MyStack s = new MyStack(); s.push( 3 ); s.push( 5 ); s.getMin(); s.push( 2 ); s.push( 1 ); s.getMin(); s.pop(); s.getMin(); s.pop(); s.peek(); } } |
Python 3
# Class to make a Node class Node: # Constructor which assign argument to nade's value def __init__( self , value): self .value = value self . next = None # This method returns the string representation of the object. def __str__( self ): return "Node({})" . format ( self .value) # __repr__ is same as __str__ __repr__ = __str__ class Stack: # Stack Constructor initialise top of stack and counter. def __init__( self ): self .top = None self .count = 0 self .minimum = None # This method returns the string representation of the object (stack). def __str__( self ): temp = self .top out = [] while temp: out.append( str (temp.value)) temp = temp. next out = '' .join(out) return ( 'Top {} Stack :{}' . format ( self .top,out)) # __repr__ is same as __str__ __repr__ = __str__ # This method is used to get minimum element of stack def getMin( self ): if self .top is None : return "Stack is empty" else : print ( "Minimum Element in the stack is: {}" . format ( self .minimum)) # Method to check if Stack is Empty or not def isEmpty( self ): # If top equals to None then stack is empty if self .top = = None : return True else : # If top not equal to None then stack is empty return False # This method returns length of stack def __len__( self ): self .count = 0 tempNode = self .top while tempNode: tempNode = tempNode. next self .count + = 1 return self .count # This method returns top of stack def peek( self ): if self .top is None : print ( "Stack is empty" ) else : if self .top.value < self .minimum: print ( "Top Most Element is: {}" . format ( self .minimum)) else : print ( "Top Most Element is: {}" . format ( self .top.value)) # This method is used to add node to stack def push( self ,value): if self .top is None : self .top = Node(value) self .minimum = value elif value < self .minimum: temp = ( 2 * value) - self .minimum new_node = Node(temp) new_node. next = self .top self .top = new_node self .minimum = value else : new_node = Node(value) new_node. next = self .top self .top = new_node print ( "Number Inserted: {}" . format (value)) # This method is used to pop top of stack def pop( self ): if self .top is None : print ( "Stack is empty" ) else : removedNode = self .top.value self .top = self .top. next if removedNode < self .minimum: print ( "Top Most Element Removed :{} " . format ( self .minimum)) self .minimum = ( ( 2 * self .minimum ) - removedNode ) else : print ( "Top Most Element Removed : {}" . format (removedNode)) # Driver program to test above class stack = Stack() stack.push( 3 ) stack.push( 5 ) stack.getMin() stack.push( 2 ) stack.push( 1 ) stack.getMin() stack.pop() stack.getMin() stack.pop() stack.peek() # This code is contributed by Blinkii |
C#
// C# program to implement a stack // that supports getMinimum() in O(1) // time and O(1) extra space. using System; using System.Collections; // A user defined stack that supports // getMin() in addition to Push() and Pop() public class MyStack { public Stack s; public int minEle; // Constructor public MyStack() { s = new Stack(); } // Prints minimum element of MyStack public void getMin() { // Get the minimum number // in the entire stack if (s.Count==0) Console.WriteLine( "Stack is empty" ); // variable minEle stores the minimum // element in the stack. else Console.WriteLine( "Minimum Element in the " + " stack is: " + minEle); } // prints top element of MyStack public void Peek() { if (s.Count==0) { Console.WriteLine( "Stack is empty " ); return ; } int t =( int )s.Peek(); // Top element. Console.Write( "Top Most Element is: " ); // If t < minEle means minEle stores // value of t. if (t < minEle) Console.WriteLine(minEle); else Console.WriteLine(t); } // Removes the top element from MyStack public void Pop() { if (s.Count==0) { Console.WriteLine( "Stack is empty" ); return ; } Console.Write( "Top Most Element Removed: " ); int t = ( int )s.Pop(); // Minimum will change as the minimum element // of the stack is being removed. if (t < minEle) { Console.WriteLine(minEle); minEle = 2*minEle - t; } else Console.WriteLine(t); } // Insert new number into MyStack public void Push( int x) { if (s.Count==0) { minEle = x; s.Push(x); Console.WriteLine( "Number Inserted: " + x); return ; } // If new number is less than original minEle if (x < minEle) { s.Push(2 * x - minEle); minEle = x; } else s.Push(x); Console.WriteLine( "Number Inserted: " + x); } } // Driver Code public class main { public static void Main(String []args) { MyStack s = new MyStack(); s.Push(3); s.Push(5); s.getMin(); s.Push(2); s.Push(1); s.getMin(); s.Pop(); s.getMin(); s.Pop(); s.Peek(); } } // This code is contributed by Arnab Kundu |
输出
Number Inserted: 3Number Inserted: 5Minimum Element in the stack is: 3Number Inserted: 2Number Inserted: 1Minimum Element in the stack is: 1Top Most Element Removed: 1Minimum Element in the stack is: 2Top Most Element Removed: 2Top Most Element is: 5
输出：
Number Inserted: 3Number Inserted: 5Minimum Element in the stack is: 3Number Inserted: 2Number Inserted: 1Minimum Element in the stack is: 1Top Most Element Removed: 1Minimum Element in the stack is: 2Top Most Element Removed: 2Top Most Element is: 5
这种方法是如何工作的？ 当要插入的元素小于minEle时，我们插入“2x–minEle”。需要注意的重要一点是，2x–minEle始终小于x（如下所示），即新minEle，当弹出此元素时，我们会看到一些不寻常的事情发生了，因为弹出的元素小于minEle。所以我们将更新minEle。
How 2*x - minEle is less than x in push()? x < minEle which means x - minEle < 0// Adding x on both sidesx - minEle + x < 0 + x 2*x - minEle < x We can conclude 2*x - minEle < new minEle
弹出时，如果我们发现元素（y）小于当前minEle，我们会发现新minEle=2*minEle–y。
How previous minimum element, prevMinEle is, 2*minEle - yin pop() is y the popped element? // We pushed y as 2x - prevMinEle. Here // prevMinEle is minEle before y was inserted y = 2*x - prevMinEle // Value of minEle was made equal to x minEle = x . new minEle = 2 * minEle - y = 2*x - (2*x - prevMinEle) = prevMinEle // This is what we wanted
练习： 类似的方法也可用于寻找最大元素。实现一个堆栈，该堆栈在O（1）时间内支持getMax（），并具有恒定的额外空间。 本文由 尼希尔·特克瓦尼。 如果你喜欢GeekSforgeks，并且想贡献自己的力量，你也可以写一篇文章，然后把你的文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
方法2：
创建一个类节点，它有两个变量val和min。val将存储我们要插入堆栈中的实际值，其中as min将存储到该节点的最小值。查看代码以便更好地理解。
JAVA
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class MinStack { Stack<Node> s; class Node{ int val; int min; public Node( int val, int min){ this .val=val; this .min=min; } } /** initialize your data structure here. */ public MinStack() { this .s= new Stack<Node>(); } public void push( int x) { if (s.isEmpty()){ this .s.push( new Node(x,x)); } else { int min=Math.min( this .s.peek().min,x); this .s.push( new Node(x,min)); } } public int pop() { return this .s.pop().val; } public int top() { return this .s.peek().val; } public int getMin() { return this .s.peek().min; } } class GFG { public static void main (String[] args) { MinStack s= new MinStack(); s.push(- 1 ); s.push( 10 ); s.push(- 4 ); s.push( 0 ); System.out.println(s.getMin()); System.out.println(s.pop()); System.out.println(s.pop()); System.out.println(s.getMin()); } } //time O(1); //it takes o(n) space since every node has to remember min value //this code is contributed by gireeshgudaparthi |
C#
/*package whatever //do not write package name here */ using System; using System.Collections.Generic; public class MinStack { Stack<Node> s; public class Node { public int val; public int min; public Node( int val, int min) { this .val = val; this .min = min; } } /** initialize your data structure here. */ public MinStack() { this .s = new Stack<Node>(); } public void push( int x) { if (s.Count==0) { this .s.Push( new Node(x, x)); } else { int min = Math.Min( this .s.Peek().min, x); this .s.Push( new Node(x, min)); } } public int pop() { return this .s.Pop().val; } public int top() { return this .s.Peek().val; } public int getMin() { return this .s.Peek().min; } } public class GFG { public static void Main(String[] args) { MinStack s = new MinStack(); s.push(-1); s.push(10); s.push(-4); s.push(0); Console.WriteLine(s.getMin()); Console.WriteLine(s.pop()); Console.WriteLine(s.pop()); Console.WriteLine(s.getMin()); } } // time O(1); // it takes o(n) space since every node has to remember min value // This code contributed by gauravrajput1 |
输出
-40-4-1
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
