devise一个堆栈，使getMinimum（）应该是O（1）
这是面试问题之一。 您需要devise一个包含整数值的堆栈，以便getMinimum（）函数返回堆栈中的最小元素。
例如：考虑下面的例子
情况1 5 - > TOP 1 4 6 2 当调用getMinimum（）时，它应该返回1，这是最小的元素 在堆栈中。 情况＃2 stack.pop（） stack.pop（） 注：5和1都从堆栈中移出。 所以在这之后，堆栈 好像， 4 - > TOP 6 2 当getMinimum（）被调用时，应该返回2，这是最小的 叠加。
制约性：
- getMinimum应返回O（1）中的最小值
- 在devise时还必须考虑空间约束，如果使用额外的空间，则空间应该是恒定的。
编辑：这不符合“恒定的空间”的约束 – 它基本上双打所需的空间。 我非常怀疑，有一个解决scheme， 虽然没有这样做，没有破坏运行的复杂性（例如做推/popupO（n））。 请注意，这不会改变所需空间的复杂性 ，例如，如果您有一个具有O（n）空间要求的堆栈，则这个值仍然是O（n），只是具有不同的常数因子。
非恒定空间解决scheme
保持“堆叠中所有值最小值”的“重复”堆栈。 当你popup主堆栈时，也popup最小堆栈。 按下主堆栈时，按下新元素或当前最小值，以较低者为准。 getMinimum()然后被实现为minStack.peek() 。
所以使用你的例子，我们有：
Real stack Min stack 5 --> TOP 1 1 1 4 2 6 2 2 2
popup两次后，你会得到：
Real stack Min stack 4 2 6 2 2 2
请让我知道，如果这是不够的信息。 当你开心的时候很简单，但是最初可能需要一点头痛）
（当然不利的一面是它占用了空间的两倍，执行时间虽然没有太大的影响，也就是说它仍然是一样的复杂度）。
编辑：有一个变化是稍微繁琐，但总体上有更好的空间。 我们仍然有最小的堆栈，但是当我们从主堆栈popup的值等于最小堆栈的值时，我们只popup它。 当被推入主堆栈的值小于或等于当前最小值时，我们只推送最小堆栈。 这允许重复的最小值。 getMinimum()仍然只是一个窥视操作。 例如，取出原来的版本，再按1，我们会得到：
Real stack Min stack 1 --> TOP 1 5 1 1 2 4 6 2
从上面的pop中popup来，因为1 == 1，所以留下：
Real stack Min stack 5 --> TOP 1 1 2 4 6 2
再次popup只会从主栈popup，因为5> 1：
Real stack Min stack 1 1 4 2 6 2
popup再次popup两个堆栈，因为1 == 1：
Real stack Min stack 4 2 6 2
如果我们很less得到一个“新的最小值或者相等的值”，这最终会导致相同的最坏情况下的空间复杂性（原来的两倍），但是空间利用率要好得多。
编辑：这是皮特的邪恶计划的实施。 我没有彻底testing过，但我认为没关系:)
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（）将不得不做更多的工作。
如果popup最小值，Pop（）将是O（n），否则它们仍然是O（1）。 当resizePush（）成为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时popup3，则看到popup的值小于min，则反转该过程以得到新的min的7，然后返回previous分钟）。 由于任何不会导致变化的值，当前最小值大于当前最小值，因此您可以使用某些值来区分改变最小值和不改变值的值。
在使用固定大小整数的语言中，您从值的表示中借用了一些空间，所以它可能会下溢，并且断言将失败。 但除此之外，它是不变的额外空间，所有的操作仍然是O（1）。
基于链接列表的堆栈还有其他可以借用的地方，例如C是下一个指针的最低有效位，或者是Java中链接列表中对象的types。 对于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）。 他们在实践中不需要更多的空间，因为他们利用这些语言中的数字，对象或指针的表示漏洞。 但是使用更紧凑表示的理论机器在每种情况下都需要额外增加一点。
那么， push和pop的运行时限制是什么？ 如果它们不是必须是常数，那么只需计算这两个操作中的最小值（使它们成为O （ n ））。 否则，我不知道如何以恒定的额外空间做到这一点。
我find了一个解决scheme，满足所有的限制（恒定时间操作）和恒定的额外空间 。
这个想法是存储最小值和input数量之间的差异，如果最小值不再是最小值，则更新最小值。
代码如下：
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
这是我的代码与O（1）运行。 我发布的前面的代码在最小元素被popup时有问题。 我修改了我的代码。 这一个使用另一个堆栈，维护当前推送元素上方的堆栈中的最小元素。
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
尝试一下。 我认为它回答了这个问题。 每一对的第二个元素给出插入元素时所看到的最小值。
我在这里发布完整的代码来查找给定堆栈中的最小值和最大值。
时间复杂度将是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()); } }
让我知道你是否面临任何问题
谢谢，Vikash
这是我的版本的实现。
struct MyStack {
int元素;
int * CurrentMiniAddress;
};
void Push（int value）
{
/ /创build你的结构和填充值
MyStack S = new MyStack（）;
S-> element = value;
如果（Stack.Empty（））
{
//由于堆栈是空的，将CurrentMiniAddress指向自身
S-> CurrentMiniAddress = S;
}
其他
{
//堆栈不是空的
/ /检索顶部的元素。 没有stream行（）
MyStack * TopElement = Stack.Top（）;
//记得总是TOP元素指向
//整个堆栈中的最小元素
如果（S->元素CurrentMiniAddress->元素）
{
//如果当前值是整个堆栈中的最小值
//然后S指向自己
S-> CurrentMiniAddress = S;
}
其他
{
//所以这不是整个堆栈中的最小值
//不用担心，TOP是最小的元素
S-> CurrentMiniAddress = TopElement-> CurrentMiniAddress;
}
}
Stack.Add（S）;
}
void Pop（）
{
如果（！Stack.Empty（））
{
Stack.Pop（）;
}
}
int GetMinimum（Stack＆stack）
{
如果（！stack.Empty（））
{
MyStack * Top = stack.top（）;
// Top总是指向minimumx
返回Top-> CurrentMiniAddress-> element;
}
}
公开课MinStack {
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); }
}
#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); } }
我在这里find这个解决scheme
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 } }
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); } }
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）运行。 这里我使用了vector对，它包含了被压入的值，也包含了这个被压入的值的最小值。
这是我的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 */
寻找用户devise对象堆栈中的最小值的实际实现，命名为：School
该堆栈将根据在特定地区为学校分配的排名将学校存储在堆栈中，例如，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; } }
This Example covers the following: 1. Implementation of Stack for User defined Objects, here, School 2. Implementation for the hashcode() and equals() method using all fields of Objects to be compared 3. A practical implementation for the scenario where we rqeuire to get the Stack contains operation to be in order of O(1)
Here's the PHP implementation of what explained in Jon Skeet's answer as the slightly better space complexity implementation to get the maximum of stack in 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
Here is the C++ implementation of Jon Skeets Answer . It might not be the most optimal way of implementing it, but it does exactly what it's supposed to.
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; } };
And here is the driver for the class
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
We can do this in O(n) time and O(1) space complexity, like so:
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
You could extend your original stack class and just add the min tracking to it. Let the original parent class handle everything else as usual.
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(); } }
I think you can simply use a LinkedList in your stack implementation.
First time you push a value, you put this value as the linkedlist head.
then each time you push a value, if the new value < head.data, make a prepand operation ( which means the head becomes the new value )
if not, then make an append operation.
When you make a pop(), you check if min == linkedlist.head.data, if yes, then 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(); } }
Here is my solution in java using liked list.
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; }
}
I think only push operation suffers, is enough. My implementation includes a stack of nodes. Each node contain the data item and also the minimum on that moment. This minimum is updated each time a push operation is done.
Here are some points for understanding:
-
I implemented the stack using Linked List.
-
A pointer top always points to the last pushed item. When there is no item in that stack top is NULL.
-
When an item is pushed a new node is allocated which has a next pointer that points to the previous stack and top is updated to point to this new node.
Only difference with normal stack implementation is that during push it updates a member min for the new node.
Please have a look at code which is implemented in C++ for demonstration purpose.
/* * 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; } }
And the output of the program looks like this:
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.
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(); } }
