这是一道面试题。
您需要设计一个包含整数值的堆栈，以便
getMinimum()函数应返回堆栈中的最小元素。例如：
情况1
5 ← 前
1
4
6
2当 getMinimum() 被调用时，它应该返回 1，这是堆栈中的最小元素。
案例#2
stack.pop()
stack.pop()注意： 5 和 1 都从堆栈中弹出。所以在此之后，堆栈看起来像
4 ← 前
6
2当
getMinimum()被调用时，它应该返回 2，这是堆栈中的最小值。约束：
- getMinimum 应该返回 O(1) 中的最小值
- 设计时还必须考虑空间限制，如果您使用额外的空间，它应该是恒定的空间。
编辑：这使“恒定空间”约束失败 - 它基本上使所需空间增加了一倍。我非常怀疑是否有一种解决方案不能做到这一点，而不会破坏某处的运行时复杂性（例如，使 push/pop O(n)）。请注意，这不会改变所需空间的复杂性，例如，如果您有一个具有 O(n) 空间要求的堆栈，这仍然是 O(n)，只是具有不同的常数因子。
非常数空间解
保留“堆栈中所有值的最小值”的“重复”堆栈。当您弹出主堆栈时，也弹出最小堆栈。当您推送主堆栈时，推送新元素或当前最小值，以较低者为准。getMinimum()然后被实施为minStack.peek().
因此，使用您的示例，我们将拥有：
Real stack Min stack
5 --> TOP 1
1 1
4 2
6 2
2 2
弹出两次后，您得到：
Real stack Min stack
4 2
6 2
2 2
如果这不是足够的信息，请告诉我。摸起来很简单，但一开始可能会有点头疼:)
（当然，缺点是它使空间需求增加了一倍。执行时间并没有显着受到影响 - 即它仍然是相同的复杂性。）
编辑：有一个变体稍微复杂一些，但总体上具有更好的空间。我们仍然有最小堆栈，但只有当我们从主堆栈弹出的值等于最小堆栈上的值时，我们才会从它弹出。只有当被压入主堆栈的值小于或等于当前最小值时，我们才会压入最小堆栈。这允许重复的最小值。仍然只是一个偷看操作。例如，获取原始版本并再次推送 1，我们会得到：getMinimum()
Real stack Min stack
1 --> TOP 1
5 1
1 2
4
6
2
因为 1 == 1，所以从上面的两个堆栈中弹出，留下：
Real stack Min stack
5 --> TOP 1
1 2
4
6
2
再次弹出仅从主堆栈中弹出，因为 5 > 1：
Real stack Min stack
1 1
4 2
6
2
再次弹出会弹出两个堆栈，因为 1 == 1：
Real stack Min stack
4 2
6
2
这最终会得到相同的最坏情况空间复杂度（原始堆栈的两倍），但如果我们很少获得“新的最小值或相等”，则空间使用会更好。
编辑：这是皮特邪恶计划的实现。我没有彻底测试过，但我认为没关系:)
using System.Collections.Generic;
public class FastMinStack<T>
{
private readonly Stack<T> stack = new Stack<T>();
// Could pass this in to the constructor
private readonly IComparer<T> comparer = Comparer<T>.Default;
private T currentMin;
public T Minimum
{
get { return currentMin; }
}
public void Push(T element)
{
if (stack.Count == 0 ||
comparer.Compare(element, currentMin) <= 0)
{
stack.Push(currentMin);
stack.Push(element);
currentMin = element;
}
else
{
stack.Push(element);
}
}
public T Pop()
{
T ret = stack.Pop();
if (comparer.Compare(ret, currentMin) == 0)
{
currentMin = stack.Pop();
}
return ret;
}
}
添加一个字段来保存最小值并在 Pop() 和 Push() 期间对其进行更新。这样 getMinimum() 将是 O(1)，但 Pop() 和 Push() 将不得不做更多的工作。
如果弹出最小值，Pop() 将是 O(n)，否则它们仍然是 O(1)。当根据 Stack 实现调整 Push() 的大小时，O(n) 变为 O(n)。
这是一个快速实现
public sealed class MinStack {
private int MinimumValue;
private readonly Stack<int> Stack = new Stack<int>();
public int GetMinimum() {
if (IsEmpty) {
throw new InvalidOperationException("Stack is empty");
}
return MinimumValue;
}
public int Pop() {
var value = Stack.Pop();
if (value == MinimumValue) {
MinimumValue = Stack.Min();
}
return value;
}
public void Push(int value) {
if (IsEmpty || value < MinimumValue) {
MinimumValue = value;
}
Stack.Push(value);
}
private bool IsEmpty { get { return Stack.Count() == 0; } }
}
public class StackWithMin {
int min;
int size;
int[] data = new int[1024];
public void push ( int val ) {
if ( size == 0 ) {
data[size] = val;
min = val;
} else if ( val < min) {
data[size] = 2 * val - min;
min = val;
assert (data[size] < min);
} else {
data[size] = val;
}
++size;
// check size and grow array
}
public int getMin () {
return min;
}
public int pop () {
--size;
int val = data[size];
if ( ( size > 0 ) && ( val < min ) ) {
int prevMin = min;
min += min - val;
return prevMin;
} else {
return val;
}
}
public boolean isEmpty () {
return size == 0;
}
public static void main (String...args) {
StackWithMin stack = new StackWithMin();
for ( String arg: args )
stack.push( Integer.parseInt( arg ) );
while ( ! stack.isEmpty() ) {
int min = stack.getMin();
int val = stack.pop();
System.out.println( val + " " + min );
}
System.out.println();
}
}
它显式存储当前最小值，如果最小值发生变化，而不是推送值，它会推送新最小值的另一侧相同差异的值（如果 min = 7 并且您推送 5，它会推送 3（5- |7-5| = 3) 并将 min 设置为 5；如果在 min 为 5 时弹出 3，它会看到弹出的值小于 min，因此反转过程以获取新 min 的 7，然后返回前一个分钟）。由于任何不会导致当前最小值发生变化的值都大于当前最小值，因此您可以使用一些东西来区分更改最小值的值和不更改最小值的值。
在使用固定大小整数的语言中，您从值的表示中借用了一些空间，因此它可能下溢并且断言将失败。但除此之外，它是恒定的额外空间，所有操作仍然是 O(1)。
相反，基于链表的堆栈还有其他可以借用的地方，例如在 C 中是 next 指针的最低有效位，或者在 Java 中是链表中对象的类型。对于 Java，这确实意味着与连续堆栈相比使用了更多空间，因为每个链接都有对象开销：
public class LinkedStackWithMin {
private static class Link {
final int value;
final Link next;
Link ( int value, Link next ) {
this.value = value;
this.next = next;
}
int pop ( LinkedStackWithMin stack ) {
stack.top = next;
return value;
}
}
private static class MinLink extends Link {
MinLink ( int value, Link next ) {
super( value, next );
}
int pop ( LinkedStackWithMin stack ) {
stack.top = next;
int prevMin = stack.min;
stack.min = value;
return prevMin;
}
}
Link top;
int min;
public LinkedStackWithMin () {
}
public void push ( int val ) {
if ( ( top == null ) || ( val < min ) ) {
top = new MinLink(min, top);
min = val;
} else {
top = new Link(val, top);
}
}
public int pop () {
return top.pop(this);
}
public int getMin () {
return min;
}
public boolean isEmpty () {
return top == null;
}
在 C 中，开销不存在，您可以借用下一个指针的 lsb：
typedef struct _stack_link stack_with_min;
typedef struct _stack_link stack_link;
struct _stack_link {
size_t next;
int value;
};
stack_link* get_next ( stack_link* link )
{
return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
}
bool is_min ( stack_link* link )
{
return ( link -> next & 1 ) ! = 0;
}
void push ( stack_with_min* stack, int value )
{
stack_link *link = malloc ( sizeof( stack_link ) );
link -> next = ( size_t ) stack -> next;
if ( (stack -> next == 0) || ( value == stack -> value ) ) {
link -> value = stack -> value;
link -> next |= 1; // mark as min
} else {
link -> value = value;
}
stack -> next = link;
}
etc.;
然而，这些都不是真正的 O(1)。它们在实践中不需要更多空间，因为它们利用了这些语言中数字、对象或指针的表示形式中的漏洞。但是使用更紧凑表示的理论机器将需要在每种情况下向该表示添加额外的位。
我找到了一个满足所有提到的约束（恒定时间操作）和恒定额外空间的解决方案。
这个想法是存储最小值和输入数字之间的差异，如果不再是最小值，则更新最小值。
代码如下：
public class MinStack {
long min;
Stack<Long> stack;
public MinStack(){
stack = new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()) {
stack.push(0L);
min = x;
} else {
stack.push(x - min); //Could be negative if min value needs to change
if (x < min) min = x;
}
}
public int pop() {
if (stack.isEmpty()) return;
long pop = stack.pop();
if (pop < 0) {
long ret = min
min = min - pop; //If negative, increase the min value
return (int)ret;
}
return (int)(pop + min);
}
public int top() {
long top = stack.peek();
if (top < 0) {
return (int)min;
} else {
return (int)(top + min);
}
}
public int getMin() {
return (int)min;
}
}
归功于：https ://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack
那么， 和 的运行时约束是push什么pop？如果它们不需要保持不变，那么只需计算这两个操作中的最小值（使它们成为O ( n )）。否则，我看不出如何通过不断增加的空间来做到这一点。
假设我们将要处理的堆栈是这样的：
6 , minvalue=2
2 , minvalue=2
5 , minvalue=3
3 , minvalue=3
9 , minvalue=7
7 , minvalue=7
8 , minvalue=8
在上面的表示中，堆栈仅由左值构建，右值的 [minvalue] 仅用于说明目的，将存储在一个变量中。
实际的问题是当最小值的值被删除时：在这一点上，我们如何知道下一个最小元素是什么而不迭代堆栈。
例如，在我们的堆栈中，当 6 被弹出时，我们知道这不是最小元素，因为最小元素是 2，所以我们可以安全地删除它而无需更新我们的最小值。
但是当我们弹出 2 时，我们可以看到最小值现在是 2，如果它被弹出，那么我们需要将最小值更新为 3。
要点1：
现在，如果您仔细观察，我们需要从这个特定状态 [2 , minvalue=2] 生成 minvalue=3。
或者如果你在堆栈中更深，我们需要从这个特定状态 [3，minvalue=3] 生成 minvalue=7，
或者如果你在堆栈中更深入，那么我们需要从这个特定状态 [7，最小值=7]
您是否注意到以上三种情况的共同点？我们需要生成的值取决于两个相等的变量。正确的。
为什么会发生这种情况，因为当我们推送一些小于当前最小值的元素时，我们基本上会将那个元素推送到堆栈中，并在最小值中更新相同的数字。
要点2：
因此，我们基本上将相同数字的副本存储一次在堆栈中，一次存储在 minvalue 变量中。
我们需要专注于避免这种重复并将一些有用的数据存储在堆栈或最小值中以生成先前的最小值，如上面的 CASES 所示。
让我们关注当要存储在 push 中的值小于最小值时，我们应该在堆栈中存储什么。让我们将此变量命名为 y，因此现在我们的堆栈将如下所示：
6 , minvalue=2
y1 , minvalue=2
5 , minvalue=3
y2 , minvalue=3
9 , minvalue=7
y3 , minvalue=7
8 , minvalue=8
我已将它们重命名为 y1,y2,y3 以避免混淆它们都将具有相同的值。
要点3：
现在让我们尝试在 y1、y2 和 y3 上找到一些约束。你还记得我们在执行 pop() 时究竟何时需要更新最小值，只有当我们弹出等于最小值的元素时。
如果我们弹出大于最小值的东西，那么我们不必更新最小值。
所以要触发minvalue的更新，y1,y2&y3应该小于对应的minvalue。[我们避免相等以避免重复[Point2]]
，因此约束是[ y < minValue ]。
现在让我们回过头来填充 y，我们需要在 push 的时候生成一些值并放入 y，记住。
让我们将推送的值设为小于 prevMinvalue 的 x，并将实际推送到堆栈中的值设为 y。
所以一件事是显而易见的，newMinValue=x，并且 y < newMinvalue。
现在我们需要在 prevMinvalue 和 x(newMinvalue) 的帮助下计算 y（记住 y 可以是任何小于 newMinValue(x) 的数字，所以我们需要找到一些可以满足我们约束的数字）。
Let's do the math:
x < prevMinvalue [Given]
x - prevMinvalue < 0
x - prevMinValue + x < 0 + x [Add x on both side]
2*x - prevMinValue < x
this is the y which we were looking for less than x(newMinValue).
y = 2*x - prevMinValue. 'or' y = 2*newMinValue - prevMinValue 'or' y = 2*curMinValue - prevMinValue [taking curMinValue=newMinValue].
因此，在推送 x 时，如果它小于 prevMinvalue，那么我们推送 y[2*x-prevMinValue] 并更新 newMinValue = x 。
在弹出时，如果堆栈包含的内容少于 minValue，那么这就是我们更新 minValue 的触发器。我们必须从 curMinValue 和 y 计算 prevMinValue。
y = 2*curMinValue - prevMinValue [证明]
prevMinValue = 2*curMinvalue - y 。
2*curMinValue - y 是我们现在需要更新为 prevMinValue 的数字。
下面共享相同逻辑的代码，时间复杂度为 O(1)，空间复杂度为 O(1)。
// C++ program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
// A user defined stack that supports getMin() in
// addition to push() and pop()
struct MyStack
{
stack<int> s;
int minEle;
// Prints minimum element of MyStack
void getMin()
{
if (s.empty())
cout << "Stack is empty\n";
// variable minEle stores the minimum element
// in the stack.
else
cout <<"Minimum Element in the stack is: "
<< minEle << "\n";
}
// Prints top element of MyStack
void peek()
{
if (s.empty())
{
cout << "Stack is empty ";
return;
}
int t = s.top(); // Top element.
cout << "Top Most Element is: ";
// If t < minEle means minEle stores
// value of t.
(t < minEle)? cout << minEle: cout << t;
}
// Remove the top element from MyStack
void pop()
{
if (s.empty())
{
cout << "Stack is empty\n";
return;
}
cout << "Top Most Element Removed: ";
int t = s.top();
s.pop();
// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
cout << minEle << "\n";
minEle = 2*minEle - t;
}
else
cout << t << "\n";
}
// Removes top element from MyStack
void push(int x)
{
// Insert new number into the stack
if (s.empty())
{
minEle = x;
s.push(x);
cout << "Number Inserted: " << x << "\n";
return;
}
// If new number is less than minEle
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
else
s.push(x);
cout << "Number Inserted: " << x << "\n";
}
};
// Driver Code
int main()
{
MyStack s;
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
return 0;
}
我们可以在 O(n) 时间和 O(1) 空间复杂度内做到这一点，如下所示：
class MinStackOptimized:
def __init__(self):
self.stack = []
self.min = None
def push(self, x):
if not self.stack:
# stack is empty therefore directly add
self.stack.append(x)
self.min = x
else:
"""
Directly add (x-self.min) to the stack. This also ensures anytime we have a
negative number on the stack is when x was less than existing minimum
recorded thus far.
"""
self.stack.append(x-self.min)
if x < self.min:
# Update x to new min
self.min = x
def pop(self):
x = self.stack.pop()
if x < 0:
"""
if popped element was negative therefore this was the minimum
element, whose actual value is in self.min but stored value is what
contributes to get the next min. (this is one of the trick we use to ensure
we are able to get old minimum once current minimum gets popped proof is given
below in pop method), value stored during push was:
(x - self.old_min) and self.min = x therefore we need to backtrack
these steps self.min(current) - stack_value(x) actually implies to
x (self.min) - (x - self.old_min)
which therefore gives old_min back and therefore can now be set
back as current self.min.
"""
self.min = self.min - x
def top(self):
x = self.stack[-1]
if x < 0:
"""
As discussed above anytime there is a negative value on stack, this
is the min value so far and therefore actual value is in self.min,
current stack value is just for getting the next min at the time
this gets popped.
"""
return self.min
else:
"""
if top element of the stack was positive then it's simple, it was
not the minimum at the time of pushing it and therefore what we did
was x(actual) - self.min(min element at current stage) let's say `y`
therefore we just need to reverse the process to get the actual
value. Therefore self.min + y, which would translate to
self.min + x(actual) - self.min, thereby giving x(actual) back
as desired.
"""
return x + self.min
def getMin(self):
# Always self.min variable holds the minimum so for so easy peezy.
return self.min
这是我的实现版本。
结构 MyStack {
整数元素；
int *CurrentMiniAddress;
};
无效推送（整数值）
{
// 创建你的结构并填充值
MyStack S = new MyStack();
S->元素=值；
如果（堆栈。空（））
{
// 由于栈是空的，所以将 CurrentMiniAddress 指向自身
S->CurrentMiniAddress = S;
}
别的
{
// 栈不为空
// 获取顶部元素。没有流行音乐（）
MyStack *TopElement = Stack.Top();
// 记住 TOP 元素总是指向
//整个堆栈中的最小元素
if (S->element CurrentMiniAddress->element)
{
// 如果当前值是整个栈中的最小值
// 然后 S 指向它自己
S->CurrentMiniAddress = S;
}
别的
{
// 所以这不是整个堆栈中的最小值
// 不用担心，TOP 持有最小元素
S->CurrentMiniAddress = TopElement->CurrentMiniAddress;
}
}
堆栈。添加（S）；
}
无效流行（）
{
if(!Stack.Empty())
{
堆栈.Pop();
}
}
int GetMinimum(堆栈 &stack)
{
如果（！stack.Empty（））
{
MyStack *Top = stack.top();
// 顶部总是指向最小值x
返回顶部->CurrentMiniAddress->元素；
}
}
这是我的代码，它以 O(1) 运行。我之前发布的代码在弹出最小元素时出现问题。我修改了我的代码。这个使用另一个 Stack 来维护当前推送元素上方的堆栈中存在的最小元素。
class StackDemo
{
int[] stk = new int[100];
int top;
public StackDemo()
{
top = -1;
}
public void Push(int value)
{
if (top == 100)
Console.WriteLine("Stack Overflow");
else
stk[++top] = value;
}
public bool IsEmpty()
{
if (top == -1)
return true;
else
return false;
}
public int Pop()
{
if (IsEmpty())
{
Console.WriteLine("Stack Underflow");
return 0;
}
else
return stk[top--];
}
public void Display()
{
for (int i = top; i >= 0; i--)
Console.WriteLine(stk[i]);
}
}
class MinStack : StackDemo
{
int top;
int[] stack = new int[100];
StackDemo s1; int min;
public MinStack()
{
top = -1;
s1 = new StackDemo();
}
public void PushElement(int value)
{
s1.Push(value);
if (top == 100)
Console.WriteLine("Stack Overflow");
if (top == -1)
{
stack[++top] = value;
stack[++top] = value;
}
else
{
// stack[++top]=value;
int ele = PopElement();
stack[++top] = ele;
int a = MininmumElement(min, value);
stack[++top] = min;
stack[++top] = value;
stack[++top] = a;
}
}
public int PopElement()
{
if (top == -1)
return 1000;
else
{
min = stack[top--];
return stack[top--];
}
}
public int PopfromStack()
{
if (top == -1)
return 1000;
else
{
s1.Pop();
return PopElement();
}
}
public int MininmumElement(int a,int b)
{
if (a > b)
return b;
else
return a;
}
public int StackTop()
{
return stack[top];
}
public void DisplayMinStack()
{
for (int i = top; i >= 0; i--)
Console.WriteLine(stack[i]);
}
}
class Program
{
static void Main(string[] args)
{
MinStack ms = new MinStack();
ms.PushElement(15);
ms.PushElement(2);
ms.PushElement(1);
ms.PushElement(13);
ms.PushElement(5);
ms.PushElement(21);
Console.WriteLine("Min Stack");
ms.DisplayMinStack();
Console.WriteLine("Minimum Element:"+ms.StackTop());
ms.PopfromStack();
ms.PopfromStack();
ms.PopfromStack();
ms.PopfromStack();
Console.WriteLine("Min Stack");
ms.DisplayMinStack();
Console.WriteLine("Minimum Element:" + ms.StackTop());
Thread.Sleep(1000000);
}
}
我使用了另一种堆栈。这是实现。
//
// main.cpp
// Eighth
//
// Created by chaitanya on 4/11/13.
// Copyright (c) 2013 cbilgika. All rights reserved.
//
#include <iostream>
#include <limits>
using namespace std;
struct stack
{
int num;
int minnum;
}a[100];
void push(int n,int m,int &top)
{
top++;
if (top>=100) {
cout<<"Stack Full";
cout<<endl;
}
else{
a[top].num = n;
a[top].minnum = m;
}
}
void pop(int &top)
{
if (top<0) {
cout<<"Stack Empty";
cout<<endl;
}
else{
top--;
}
}
void print(int &top)
{
cout<<"Stack: "<<endl;
for (int j = 0; j<=top ; j++) {
cout<<"("<<a[j].num<<","<<a[j].minnum<<")"<<endl;
}
}
void get_min(int &top)
{
if (top < 0)
{
cout<<"Empty Stack";
}
else{
cout<<"Minimum element is: "<<a[top].minnum;
}
cout<<endl;
}
int main()
{
int top = -1,min = numeric_limits<int>::min(),num;
cout<<"Enter the list to push (-1 to stop): ";
cin>>num;
while (num!=-1) {
if (top == -1) {
min = num;
push(num, min, top);
}
else{
if (num < min) {
min = num;
}
push(num, min, top);
}
cin>>num;
}
print(top);
get_min(top);
return 0;
}
输出：
Enter the list to push (-1 to stop): 5
1
4
6
2
-1
Stack:
(5,5)
(1,1)
(4,1)
(6,1)
(2,1)
Minimum element is: 1
尝试一下。我认为它回答了这个问题。每对的第二个元素给出插入该元素时看到的最小值。
public class MinStack<E>{
private final LinkedList<E> mainStack = new LinkedList<E>();
private final LinkedList<E> minStack = new LinkedList<E>();
private final Comparator<E> comparator;
public MinStack(Comparator<E> comparator)
{
this.comparator = comparator;
}
/**
* Pushes an element onto the stack.
*
*
* @param e the element to push
*/
public void push(E e) {
mainStack.push(e);
if(minStack.isEmpty())
{
minStack.push(e);
}
else if(comparator.compare(e, minStack.peek())<=0)
{
minStack.push(e);
}
else
{
minStack.push(minStack.peek());
}
}
/**
* Pops an element from the stack.
*
*
* @throws NoSuchElementException if this stack is empty
*/
public E pop() {
minStack.pop();
return mainStack.pop();
}
/**
* Returns but not remove smallest element from the stack. Return null if stack is empty.
*
*/
public E getMinimum()
{
return minStack.peek();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Main stack{");
for (E e : mainStack) {
sb.append(e.toString()).append(",");
}
sb.append("}");
sb.append(" Min stack{");
for (E e : minStack) {
sb.append(e.toString()).append(",");
}
sb.append("}");
sb.append(" Minimum = ").append(getMinimum());
return sb.toString();
}
public static void main(String[] args) {
MinStack<Integer> st = new MinStack<Integer>(Comparators.INTEGERS);
st.push(2);
Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
System.out.println(st);
st.push(6);
Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
System.out.println(st);
st.push(4);
Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
System.out.println(st);
st.push(1);
Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
System.out.println(st);
st.push(5);
Assert.assertTrue("1 is min in stack {2,6,4,1,5}", st.getMinimum().equals(1));
System.out.println(st);
st.pop();
Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
System.out.println(st);
st.pop();
Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
System.out.println(st);
st.pop();
Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
System.out.println(st);
st.pop();
Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
System.out.println(st);
st.pop();
Assert.assertTrue("null is min in stack {}", st.getMinimum()==null);
System.out.println(st);
}
}
我在此处发布完整代码以在给定堆栈中查找最小值和最大值。
时间复杂度将是 O(1)..
package com.java.util.collection.advance.datastructure;
/**
*
* @author vsinha
*
*/
public abstract interface Stack<E> {
/**
* Placing a data item on the top of the stack is called pushing it
* @param element
*
*/
public abstract void push(E element);
/**
* Removing it from the top of the stack is called popping it
* @return the top element
*/
public abstract E pop();
/**
* Get it top element from the stack and it
* but the item is not removed from the stack, which remains unchanged
* @return the top element
*/
public abstract E peek();
/**
* Get the current size of the stack.
* @return
*/
public abstract int size();
/**
* Check whether stack is empty of not.
* @return true if stack is empty, false if stack is not empty
*/
public abstract boolean empty();
}
package com.java.util.collection.advance.datastructure;
@SuppressWarnings("hiding")
public abstract interface MinMaxStack<Integer> extends Stack<Integer> {
public abstract int min();
public abstract int max();
}
package com.java.util.collection.advance.datastructure;
import java.util.Arrays;
/**
*
* @author vsinha
*
* @param <E>
*/
public class MyStack<E> implements Stack<E> {
private E[] elements =null;
private int size = 0;
private int top = -1;
private final static int DEFAULT_INTIAL_CAPACITY = 10;
public MyStack(){
// If you don't specify the size of stack. By default, Stack size will be 10
this(DEFAULT_INTIAL_CAPACITY);
}
@SuppressWarnings("unchecked")
public MyStack(int intialCapacity){
if(intialCapacity <=0){
throw new IllegalArgumentException("initial capacity can't be negative or zero");
}
// Can't create generic type array
elements =(E[]) new Object[intialCapacity];
}
@Override
public void push(E element) {
ensureCapacity();
elements[++top] = element;
++size;
}
@Override
public E pop() {
E element = null;
if(!empty()) {
element=elements[top];
// Nullify the reference
elements[top] =null;
--top;
--size;
}
return element;
}
@Override
public E peek() {
E element = null;
if(!empty()) {
element=elements[top];
}
return element;
}
@Override
public int size() {
return size;
}
@Override
public boolean empty() {
return size == 0;
}
/**
* Increases the capacity of this <tt>Stack by double of its current length</tt> instance,
* if stack is full
*/
private void ensureCapacity() {
if(size != elements.length) {
// Don't do anything. Stack has space.
} else{
elements = Arrays.copyOf(elements, size *2);
}
}
@Override
public String toString() {
return "MyStack [elements=" + Arrays.toString(elements) + ", size="
+ size + ", top=" + top + "]";
}
}
package com.java.util.collection.advance.datastructure;
/**
* Time complexity will be O(1) to find min and max in a given stack.
* @author vsinha
*
*/
public class MinMaxStackFinder extends MyStack<Integer> implements MinMaxStack<Integer> {
private MyStack<Integer> minStack;
private MyStack<Integer> maxStack;
public MinMaxStackFinder (int intialCapacity){
super(intialCapacity);
minStack =new MyStack<Integer>();
maxStack =new MyStack<Integer>();
}
public void push(Integer element) {
// Current element is lesser or equal than min() value, Push the current element in min stack also.
if(!minStack.empty()) {
if(min() >= element) {
minStack.push(element);
}
} else{
minStack.push(element);
}
// Current element is greater or equal than max() value, Push the current element in max stack also.
if(!maxStack.empty()) {
if(max() <= element) {
maxStack.push(element);
}
} else{
maxStack.push(element);
}
super.push(element);
}
public Integer pop(){
Integer curr = super.pop();
if(curr !=null) {
if(min() == curr) {
minStack.pop();
}
if(max() == curr){
maxStack.pop();
}
}
return curr;
}
@Override
public int min() {
return minStack.peek();
}
@Override
public int max() {
return maxStack.peek();
}
@Override
public String toString() {
return super.toString()+"\nMinMaxStackFinder [minStack=" + minStack + "\n maxStack="
+ maxStack + "]" ;
}
}
// You can use the below program to execute it.
package com.java.util.collection.advance.datastructure;
import java.util.Random;
public class MinMaxStackFinderApp {
public static void main(String[] args) {
MinMaxStack<Integer> stack =new MinMaxStackFinder(10);
Random random =new Random();
for(int i =0; i< 10; i++){
stack.push(random.nextInt(100));
}
System.out.println(stack);
System.out.println("MAX :"+stack.max());
System.out.println("MIN :"+stack.min());
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack);
System.out.println("MAX :"+stack.max());
System.out.println("MIN :"+stack.min());
}
}
如果您遇到任何问题，请告诉我
谢谢， 维卡什
class MyStackImplementation{
private final int capacity = 4;
int min;
int arr[] = new int[capacity];
int top = -1;
public void push ( int val ) {
top++;
if(top <= capacity-1){
if(top == 0){
min = val;
arr[top] = val;
}
else if(val < min){
arr[top] = arr[top]+min;
min = arr[top]-min;
arr[top] = arr[top]-min;
}
else {
arr[top] = val;
}
System.out.println("element is pushed");
}
else System.out.println("stack is full");
}
public void pop () {
top--;
if(top > -1){
min = arr[top];
}
else {min=0; System.out.println("stack is under flow");}
}
public int min(){
return min;
}
public boolean isEmpty () {
return top == 0;
}
public static void main(String...s){
MyStackImplementation msi = new MyStackImplementation();
msi.push(1);
msi.push(4);
msi.push(2);
msi.push(10);
System.out.println(msi.min);
msi.pop();
msi.pop();
msi.pop();
msi.pop();
msi.pop();
System.out.println(msi.min);
}
}
这是Jon Skeet 的回答中解释的 PHP 实现，它是在 O(1) 中获得最大堆栈的稍微更好的空间复杂度实现。
<?php
/**
* An ordinary stack implementation.
*
* In real life we could just extend the built-in "SplStack" class.
*/
class BaseIntegerStack
{
/**
* Stack main storage.
*
* @var array
*/
private $storage = [];
// ------------------------------------------------------------------------
// Public API
// ------------------------------------------------------------------------
/**
* Pushes to stack.
*
* @param int $value New item.
*
* @return bool
*/
public function push($value)
{
return is_integer($value)
? (bool) array_push($this->storage, $value)
: false;
}
/**
* Pops an element off the stack.
*
* @return int
*/
public function pop()
{
return array_pop($this->storage);
}
/**
* See what's on top of the stack.
*
* @return int|bool
*/
public function top()
{
return empty($this->storage)
? false
: end($this->storage);
}
// ------------------------------------------------------------------------
// Magic methods
// ------------------------------------------------------------------------
/**
* String representation of the stack.
*
* @return string
*/
public function __toString()
{
return implode('|', $this->storage);
}
} // End of BaseIntegerStack class
/**
* The stack implementation with getMax() method in O(1).
*/
class Stack extends BaseIntegerStack
{
/**
* Internal stack to keep track of main stack max values.
*
* @var BaseIntegerStack
*/
private $maxStack;
/**
* Stack class constructor.
*
* Dependencies are injected.
*
* @param BaseIntegerStack $stack Internal stack.
*
* @return void
*/
public function __construct(BaseIntegerStack $stack)
{
$this->maxStack = $stack;
}
// ------------------------------------------------------------------------
// Public API
// ------------------------------------------------------------------------
/**
* Prepends an item into the stack maintaining max values.
*
* @param int $value New item to push to the stack.
*
* @return bool
*/
public function push($value)
{
if ($this->isNewMax($value)) {
$this->maxStack->push($value);
}
parent::push($value);
}
/**
* Pops an element off the stack maintaining max values.
*
* @return int
*/
public function pop()
{
$popped = parent::pop();
if ($popped == $this->maxStack->top()) {
$this->maxStack->pop();
}
return $popped;
}
/**
* Finds the maximum of stack in O(1).
*
* @return int
* @see push()
*/
public function getMax()
{
return $this->maxStack->top();
}
// ------------------------------------------------------------------------
// Internal helpers
// ------------------------------------------------------------------------
/**
* Checks that passing value is a new stack max or not.
*
* @param int $new New integer to check.
*
* @return boolean
*/
private function isNewMax($new)
{
return empty($this->maxStack) OR $new > $this->maxStack->top();
}
} // End of Stack class
// ------------------------------------------------------------------------
// Stack Consumption and Test
// ------------------------------------------------------------------------
$stack = new Stack(
new BaseIntegerStack
);
$stack->push(9);
$stack->push(4);
$stack->push(237);
$stack->push(5);
$stack->push(556);
$stack->push(15);
print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n\n";
print "Pop: {$stack->pop()}\n";
print "Pop: {$stack->pop()}\n\n";
print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n\n";
print "Pop: {$stack->pop()}\n";
print "Pop: {$stack->pop()}\n\n";
print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n";
// Here's the sample output:
//
// Stack: 9|4|237|5|556|15
// Max: 556
//
// Pop: 15
// Pop: 556
//
// Stack: 9|4|237|5
// Max: 237
//
// Pop: 5
// Pop: 237
//
// Stack: 9|4
// Max: 9
class FastStack {
private static class StackNode {
private Integer data;
private StackNode nextMin;
public StackNode(Integer data) {
this.data = data;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public StackNode getNextMin() {
return nextMin;
}
public void setNextMin(StackNode nextMin) {
this.nextMin = nextMin;
}
}
private LinkedList<StackNode> stack = new LinkedList<>();
private StackNode currentMin = null;
public void push(Integer item) {
StackNode node = new StackNode(item);
if (currentMin == null) {
currentMin = node;
node.setNextMin(null);
} else if (item < currentMin.getData()) {
StackNode oldMinNode = currentMin;
node.setNextMin(oldMinNode);
currentMin = node;
}
stack.addFirst(node);
}
public Integer pop() {
if (stack.isEmpty()) {
throw new EmptyStackException();
}
StackNode node = stack.peek();
if (currentMin == node) {
currentMin = node.getNextMin();
}
stack.removeFirst();
return node.getData();
}
public Integer getMinimum() {
if (stack.isEmpty()) {
throw new NoSuchElementException("Stack is empty");
}
return currentMin.getData();
}
}
这是我的代码，它以 O(1) 运行。在这里，我使用了向量对，其中包含推送的值，还包含直到推送的值的最小值。
这是我的 C++ 实现版本。
vector<pair<int,int> >A;
int sz=0; // to keep track of the size of vector
class MinStack
{
public:
MinStack()
{
A.clear();
sz=0;
}
void push(int x)
{
int mn=(sz==0)?x: min(A[sz-1].second,x); //find the minimum value upto this pushed value
A.push_back(make_pair(x,mn));
sz++; // increment the size
}
void pop()
{
if(sz==0) return;
A.pop_back(); // pop the last inserted element
sz--; // decrement size
}
int top()
{
if(sz==0) return -1; // if stack empty return -1
return A[sz-1].first; // return the top element
}
int getMin()
{
if(sz==0) return -1;
return A[sz-1].second; // return the minimum value at sz-1
}
};
**The task can be acheived by creating two stacks:**
import java.util.Stack;
/*
*
* Find min in stack using O(n) Space Complexity
*/
public class DeleteMinFromStack {
void createStack(Stack<Integer> primary, Stack<Integer> minStack, int[] arr) {
/* Create main Stack and in parallel create the stack which contains the minimum seen so far while creating main Stack */
primary.push(arr[0]);
minStack.push(arr[0]);
for (int i = 1; i < arr.length; i++) {
primary.push(arr[i]);
if (arr[i] <= minStack.peek())// Condition to check to push the value in minimum stack only when this urrent value is less than value seen at top of this stack */
minStack.push(arr[i]);
}
}
int findMin(Stack<Integer> secStack) {
return secStack.peek();
}
public static void main(String args[]) {
Stack<Integer> primaryStack = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();
DeleteMinFromStack deleteMinFromStack = new DeleteMinFromStack();
int[] arr = { 5, 5, 6, 8, 13, 1, 11, 6, 12 };
deleteMinFromStack.createStack(primaryStack, minStack, arr);
int mimElement = deleteMinFromStack.findMin(primaryStack, minStack);
/** This check for algorithm when the main Stack Shrinks by size say i as in loop below */
for (int i = 0; i < 2; i++) {
primaryStack.pop();
}
System.out.println(" Minimum element is " + mimElement);
}
}
/*
here in have tried to add for loop wherin the main tack can be shrinked/expaned so we can check the algorithm */
一种在用户设计对象堆栈中找到最小值的实用实现，名为：School
Stack 将根据分配给特定地区学校的排名将学校存储在 Stack 中，例如，findMin() 给出了我们获得最大入学申请数量的学校，而这又由使用与上一季学校相关的排名的比较器。
The Code for same is below:
package com.practical;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
public class CognitaStack {
public School findMin(Stack<School> stack, Stack<School> minStack) {
if (!stack.empty() && !minStack.isEmpty())
return (School) minStack.peek();
return null;
}
public School removeSchool(Stack<School> stack, Stack<School> minStack) {
if (stack.isEmpty())
return null;
School temp = stack.peek();
if (temp != null) {
// if(temp.compare(stack.peek(), minStack.peek())<0){
stack.pop();
minStack.pop();
// }
// stack.pop();
}
return stack.peek();
}
public static void main(String args[]) {
Stack<School> stack = new Stack<School>();
Stack<School> minStack = new Stack<School>();
List<School> lst = new LinkedList<School>();
School s1 = new School("Polam School", "London", 3);
School s2 = new School("AKELEY WOOD SENIOR SCHOOL", "BUCKINGHAM", 4);
School s3 = new School("QUINTON HOUSE SCHOOL", "NORTHAMPTON", 2);
School s4 = new School("OAKLEIGH HOUSE SCHOOL", " SWANSEA", 5);
School s5 = new School("OAKLEIGH-OAK HIGH SCHOOL", "Devon", 1);
School s6 = new School("BritishInter2", "Devon", 7);
lst.add(s1);
lst.add(s2);
lst.add(s3);
lst.add(s4);
lst.add(s5);
lst.add(s6);
Iterator<School> itr = lst.iterator();
while (itr.hasNext()) {
School temp = itr.next();
if ((minStack.isEmpty()) || (temp.compare(temp, minStack.peek()) < 0)) { // minStack.peek().equals(temp)
stack.push(temp);
minStack.push(temp);
} else {
minStack.push(minStack.peek());
stack.push(temp);
}
}
CognitaStack cogStack = new CognitaStack();
System.out.println(" Minimum in Stack is " + cogStack.findMin(stack, minStack).name);
cogStack.removeSchool(stack, minStack);
cogStack.removeSchool(stack, minStack);
System.out.println(" Minimum in Stack is "
+ ((cogStack.findMin(stack, minStack) != null) ? cogStack.findMin(stack, minStack).name : "Empty"));
}
}
学校对象如下：
package com.practical;
import java.util.Comparator;
public class School implements Comparator<School> {
String name;
String location;
int rank;
public School(String name, String location, int rank) {
super();
this.name = name;
this.location = location;
this.rank = rank;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((location == null) ? 0 : location.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
result = prime * result + rank;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
School other = (School) obj;
if (location == null) {
if (other.location != null)
return false;
} else if (!location.equals(other.location))
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
if (rank != other.rank)
return false;
return true;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getLocation() {
return location;
}
public void setLocation(String location) {
this.location = location;
}
public int getRank() {
return rank;
}
public void setRank(int rank) {
this.rank = rank;
}
public int compare(School o1, School o2) {
// TODO Auto-generated method stub
return o1.rank - o2.rank;
}
}
class SchoolComparator implements Comparator<School> {
public int compare(School o1, School o2) {
return o1.rank - o2.rank;
}
}
该示例涵盖以下内容： 1. 用户定义对象的堆栈实现，这里是学校 2. 使用要比较的对象的所有字段实现 hashcode() 和 equals() 方法 3. 我们的场景的实际实现rqeuire 获取堆栈包含操作的顺序为 O(1)
这是 Jon Skeets Answer的 C++ 实现。它可能不是实现它的最佳方式，但它完全符合它的预期。
class Stack {
private:
struct stack_node {
int val;
stack_node *next;
};
stack_node *top;
stack_node *min_top;
public:
Stack() {
top = nullptr;
min_top = nullptr;
}
void push(int num) {
stack_node *new_node = nullptr;
new_node = new stack_node;
new_node->val = num;
if (is_empty()) {
top = new_node;
new_node->next = nullptr;
min_top = new_node;
new_node->next = nullptr;
} else {
new_node->next = top;
top = new_node;
if (new_node->val <= min_top->val) {
new_node->next = min_top;
min_top = new_node;
}
}
}
void pop(int &num) {
stack_node *tmp_node = nullptr;
stack_node *min_tmp = nullptr;
if (is_empty()) {
std::cout << "It's empty\n";
} else {
num = top->val;
if (top->val == min_top->val) {
min_tmp = min_top->next;
delete min_top;
min_top = min_tmp;
}
tmp_node = top->next;
delete top;
top = tmp_node;
}
}
bool is_empty() const {
return !top;
}
void get_min(int &item) {
item = min_top->val;
}
};
这是课程的驱动程序
int main() {
int pop, min_el;
Stack my_stack;
my_stack.push(4);
my_stack.push(6);
my_stack.push(88);
my_stack.push(1);
my_stack.push(234);
my_stack.push(2);
my_stack.get_min(min_el);
cout << "Min: " << min_el << endl;
my_stack.pop(pop);
cout << "Popped stock element: " << pop << endl;
my_stack.pop(pop);
cout << "Popped stock element: " << pop << endl;
my_stack.pop(pop);
cout << "Popped stock element: " << pop << endl;
my_stack.get_min(min_el);
cout << "Min: " << min_el << endl;
return 0;
}
输出：
Min: 1
Popped stock element: 2
Popped stock element: 234
Popped stock element: 1
Min: 4
您可以扩展您的原始堆栈类，然后将最小跟踪添加到它。让原始父类照常处理其他所有事情。
public class StackWithMin extends Stack<Integer> {
private Stack<Integer> min;
public StackWithMin() {
min = new Stack<>();
}
public void push(int num) {
if (super.isEmpty()) {
min.push(num);
} else if (num <= min.peek()) {
min.push(num);
}
super.push(num);
}
public int min() {
return min.peek();
}
public Integer pop() {
if (super.peek() == min.peek()) {
min.pop();
}
return super.pop();
}
}
我认为您可以在堆栈实现中简单地使用 LinkedList 。
第一次推送一个值时，你把这个值作为链表头。
那么每次push一个值，如果新值<head.data，做一个prepand操作（也就是说head变成了新值）
如果没有，则进行追加操作。
当你做一个 pop() 时，你检查是否 min == linkedlist.head.data，如果是，那么 head=head.next；
这是我的代码。
public class Stack {
int[] elements;
int top;
Linkedlists min;
public Stack(int n) {
elements = new int[n];
top = 0;
min = new Linkedlists();
}
public void realloc(int n) {
int[] tab = new int[n];
for (int i = 0; i < top; i++) {
tab[i] = elements[i];
}
elements = tab;
}
public void push(int x) {
if (top == elements.length) {
realloc(elements.length * 2);
}
if (top == 0) {
min.pre(x);
} else if (x < min.head.data) {
min.pre(x);
} else {
min.app(x);
}
elements[top++] = x;
}
public int pop() {
int x = elements[--top];
if (top == 0) {
}
if (this.getMin() == x) {
min.head = min.head.next;
}
elements[top] = 0;
if (4 * top < elements.length) {
realloc((elements.length + 1) / 2);
}
return x;
}
public void display() {
for (Object x : elements) {
System.out.print(x + " ");
}
}
public int getMin() {
if (top == 0) {
return 0;
}
return this.min.head.data;
}
public static void main(String[] args) {
Stack stack = new Stack(4);
stack.push(2);
stack.push(3);
stack.push(1);
stack.push(4);
stack.push(5);
stack.pop();
stack.pop();
stack.pop();
stack.push(1);
stack.pop();
stack.pop();
stack.pop();
stack.push(2);
System.out.println(stack.getMin());
stack.display();
}
}
这是我在 java 中使用喜欢列表的解决方案。
class Stack{
int min;
Node top;
static class Node{
private int data;
private Node next;
private int min;
Node(int data, int min){
this.data = data;
this.min = min;
this.next = null;
}
}
void push(int data){
Node temp;
if(top == null){
temp = new Node(data,data);
top = temp;
top.min = data;
}
if(top.min > data){
temp = new Node(data,data);
temp.next = top;
top = temp;
} else {
temp = new Node(data, top.min);
temp.next = top;
top = temp;
}
}
void pop(){
if(top != null){
top = top.next;
}
}
int min(){
return top.min;
}
}
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
namespace Solution
{
public class MinStack
{
public MinStack()
{
MainStack=new Stack<int>();
Min=new Stack<int>();
}
static Stack<int> MainStack;
static Stack<int> Min;
public void Push(int item)
{
MainStack.Push(item);
if(Min.Count==0 || item<Min.Peek())
Min.Push(item);
}
public void Pop()
{
if(Min.Peek()==MainStack.Peek())
Min.Pop();
MainStack.Pop();
}
public int Peek()
{
return MainStack.Peek();
}
public int GetMin()
{
if(Min.Count==0)
throw new System.InvalidOperationException("Stack Empty");
return Min.Peek();
}
}
}
在这里看到了一个绝妙的解决方案： https ://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/
Bellow是我按照算法编写的python代码：
class Node:
def __init__(self, value):
self.value = value
self.next = None
class MinStack:
def __init__(self):
self.head = None
self.min = float('inf')
# @param x, an integer
def push(self, x):
if self.head == None:
self.head = Node(x)
self.min = x
else:
if x >= self.min:
n = Node(x)
n.next = self.head
self.head = n
else:
v = 2 * x - self.min
n = Node(v)
n.next = self.head
self.head = n
self.min = x
# @return nothing
def pop(self):
if self.head:
if self.head.value < self.min:
self.min = self.min * 2 - self.head.value
self.head = self.head.next
# @return an integer
def top(self):
if self.head:
if self.head.value < self.min:
self.min = self.min * 2 - self.head.value
return self.min
else:
return self.head.value
else:
return -1
# @return an integer
def getMin(self):
if self.head:
return self.min
else:
return -1
从 Stack 中获取最小元素。我们必须使用两个堆栈。即堆栈 s1 和堆栈 s2。
---------------------递归调用步骤 2 到 4------------------------
如果新元素添加到堆栈 s1。然后从堆栈 s2 中弹出元素
将新元素与 s2 进行比较。哪个更小，推到s2。
从堆栈 s2 中弹出（包含最小元素）
代码如下：
package Stack;
import java.util.Stack;
public class getMin
{
Stack<Integer> s1= new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
void push(int x)
{
if(s1.isEmpty() || s2.isEmpty())
{
s1.push(x);
s2.push(x);
}
else
{
s1. push(x);
int y = (Integer) s2.pop();
s2.push(y);
if(x < y)
s2.push(x);
}
}
public Integer pop()
{
int x;
x=(Integer) s1.pop();
s2.pop();
return x;
}
public int getmin()
{
int x1;
x1= (Integer)s2.pop();
s2.push(x1);
return x1;
}
public static void main(String[] args) {
getMin s = new getMin();
s.push(10);
s.push(20);
s.push(30);
System.out.println(s.getmin());
s.push(1);
System.out.println(s.getmin());
}
}
我有更好的解决方案，使用 O(1) 时间且没有额外空间，您需要将元素作为字符串推送为 <original_value,minimum_value>。例如找到这个字符串堆栈。
|-1,-1 |
| 1,1 |
| 2,2 |
| 5,3 |
| 3,3 |
现在，您总是可以通过使用 peek 并检查给定实例的最小值来找到当前实例的最小值。这是没有额外空间的 O(1) 时间
我认为只有推送操作受到影响，就足够了。我的实现包括一堆节点。每个节点都包含数据项以及当时的最小值。每次完成推送操作时都会更新此最小值。
以下是一些理解要点：
我使用链表实现了堆栈。
指针顶部始终指向最后推送的项目。当堆栈顶部没有项目时为 NULL。
当一个项目被推入时，分配一个新节点，该节点有一个指向前一个堆栈的下一个指针，并且更新顶部以指向这个新节点。
与普通堆栈实现的唯一区别在于，在推送期间它会更新新节点的成员 min。
请查看以 C++ 实现的代码以进行演示。
/*
* Implementation of Stack that can give minimum in O(1) time all the time
* This solution uses same data structure for minimum variable, it could be implemented using pointers but that will be more space consuming
*/
#include <iostream>
using namespace std;
typedef struct stackLLNodeType stackLLNode;
struct stackLLNodeType {
int item;
int min;
stackLLNode *next;
};
class DynamicStack {
private:
int stackSize;
stackLLNode *top;
public:
DynamicStack();
~DynamicStack();
void push(int x);
int pop();
int getMin();
int size() { return stackSize; }
};
void pushOperation(DynamicStack& p_stackObj, int item);
void popOperation(DynamicStack& p_stackObj);
int main () {
DynamicStack stackObj;
pushOperation(stackObj, 3);
pushOperation(stackObj, 1);
pushOperation(stackObj, 2);
popOperation(stackObj);
popOperation(stackObj);
popOperation(stackObj);
popOperation(stackObj);
pushOperation(stackObj, 4);
pushOperation(stackObj, 7);
pushOperation(stackObj, 6);
popOperation(stackObj);
popOperation(stackObj);
popOperation(stackObj);
popOperation(stackObj);
return 0;
}
DynamicStack::DynamicStack() {
// initialization
stackSize = 0;
top = NULL;
}
DynamicStack::~DynamicStack() {
stackLLNode* tmp;
// chain memory deallocation to avoid memory leak
while (top) {
tmp = top;
top = top->next;
delete tmp;
}
}
void DynamicStack::push(int x) {
// allocate memory for new node assign to top
if (top==NULL) {
top = new stackLLNode;
top->item = x;
top->next = NULL;
top->min = top->item;
}
else {
// allocation of memory
stackLLNode *tmp = new stackLLNode;
// assign the new item
tmp->item = x;
tmp->next = top;
// store the minimum so that it does not get lost after pop operation of later minimum
if (x < top->min)
tmp->min = x;
else
tmp->min = top->min;
// update top to new node
top = tmp;
}
stackSize++;
}
int DynamicStack::pop() {
// check if stack is empty
if (top == NULL)
return -1;
stackLLNode* tmp = top;
int curItem = top->item;
top = top->next;
delete tmp;
stackSize--;
return curItem;
}
int DynamicStack::getMin() {
if (top == NULL)
return -1;
return top->min;
}
void pushOperation(DynamicStack& p_stackObj, int item) {
cout<<"Just pushed: "<<item<<endl;
p_stackObj.push(item);
cout<<"Current stack min: "<<p_stackObj.getMin()<<endl;
cout<<"Current stack size: "<<p_stackObj.size()<<endl<<endl;
}
void popOperation(DynamicStack& p_stackObj) {
int popItem = -1;
if ((popItem = p_stackObj.pop()) == -1 )
cout<<"Cannot pop. Stack is empty."<<endl;
else {
cout<<"Just popped: "<<popItem<<endl;
if (p_stackObj.getMin() == -1)
cout<<"No minimum. Stack is empty."<<endl;
else
cout<<"Current stack min: "<<p_stackObj.getMin()<<endl;
cout<<"Current stack size: "<<p_stackObj.size()<<endl<<endl;
}
}
程序的输出如下所示：
Just pushed: 3
Current stack min: 3
Current stack size: 1
Just pushed: 1
Current stack min: 1
Current stack size: 2
Just pushed: 2
Current stack min: 1
Current stack size: 3
Just popped: 2
Current stack min: 1
Current stack size: 2
Just popped: 1
Current stack min: 3
Current stack size: 1
Just popped: 3
No minimum. Stack is empty.
Current stack size: 0
Cannot pop. Stack is empty.
Just pushed: 4
Current stack min: 4
Current stack size: 1
Just pushed: 7
Current stack min: 4
Current stack size: 2
Just pushed: 6
Current stack min: 4
Current stack size: 3
Just popped: 6
Current stack min: 4
Current stack size: 2
Just popped: 7
Current stack min: 4
Current stack size: 1
Just popped: 4
No minimum. Stack is empty.
Current stack size: 0
Cannot pop. Stack is empty.
#include<stdio.h>
struct stack
{
int data;
int mindata;
}a[100];
void push(int *tos,int input)
{
if (*tos > 100)
{
printf("overflow");
return;
}
(*tos)++;
a[(*tos)].data=input;
if (0 == *tos)
a[*tos].mindata=input;
else if (a[*tos -1].mindata < input)
a[*tos].mindata=a[*tos -1].mindata;
else
a[*tos].mindata=input;
}
int pop(int * tos)
{
if (*tos <= -1)
{
printf("underflow");
return -1;
}
return(a[(*tos)--].data);
}
void display(int tos)
{
while (tos > -1)
{
printf("%d:%d\t",a[tos].data,a[tos].mindata);
tos--;
}
}
int min(int tos)
{
return(a[tos].mindata);
}
int main()
{
int tos=-1,x,choice;
while(1)
{
printf("press 1-push,2-pop,3-mindata,4-display,5-exit ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("enter data to push");
scanf("%d",&x);
push(&tos,x);
break;
case 2: printf("the poped out data=%d ",pop(&tos));
break;
case 3: printf("The min peeped data:%d",min(tos));
break;
case 4: printf("The elements of stack \n");
display(tos);
break;
default: exit(0);
}
}
struct StackGetMin {
void push(int x) {
elements.push(x);
if (minStack.empty() || x <= minStack.top())
minStack.push(x);
}
bool pop() {
if (elements.empty()) return false;
if (elements.top() == minStack.top())
minStack.pop();
elements.pop();
return true;
}
bool getMin(int &min) {
if (minStack.empty()) {
return false;
} else {
min = minStack.top();
return true;
}
}
stack<int> elements;
stack<int> minStack;
};
struct Node {
let data: Int
init(_ d:Int){
data = d
}
}
struct Stack {
private var backingStore = [Node]()
private var minArray = [Int]()
mutating func push(n:Node) {
backingStore.append(n)
minArray.append(n.data)
minArray.sort(>)
minArray
}
mutating func pop() -> Node? {
if(backingStore.isEmpty){
return nil
}
let n = backingStore.removeLast()
var found = false
minArray = minArray.filter{
if (!found && $0 == n.data) {
found = true
return false
}
return true
}
return n
}
func min() -> Int? {
return minArray.last
}
}
public interface IMinStack<T extends Comparable<T>> {
public void push(T val);
public T pop();
public T minValue();
public int size();
}
import java.util.Stack;
public class MinStack<T extends Comparable<T>> implements IMinStack<T> {
private Stack<T> stack = new Stack<T>();
private Stack<T> minStack = new Stack<T>();
@Override
public void push(T val) {
stack.push(val);
if (minStack.isEmpty() || val.compareTo(minStack.peek()) < 0)
minStack.push(val);
}
@Override
public T pop() {
T val = stack.pop();
if ((false == minStack.isEmpty())
&& val.compareTo(minStack.peek()) == 0)
minStack.pop();
return val;
}
@Override
public T minValue() {
return minStack.peek();
}
@Override
public int size() {
return stack.size();
}
}