在O（1）时间复杂度内实现栈的push，pop和findmin操作

Question

我已经看过两个关于这个问题的堆栈实现，但我真的很困惑，如何才能获得O(1)的操作。

考虑以下例子：

S1[3542761986759]
S2[3332221111111]

这里的想法/算法是：

1. 将元素 E 推入 S1
2. 检查 S2 的顶部是否 >= E，如果为真，则在 S2 中插入 E

但是当调用 getMin 时，我们返回 S2 的顶部，但这会使 S2 处于奇怪的状态，因为 S2 包含重复的当前最小元素，所以解决方案是在 S2 中搜索下一个最小元素并返回它。 这是 O(n)。

请问有人可以帮我理解这个解决方案吗？

- pappu

---

可能是[设计一个栈，使得getMinimum（）应该为O（1）]的重复问题（https://dev59.com/0nRB5IYBdhLWcg3wN1AQ） - finnw

它不是那一个的副本。它需要常量空间。这个稍微宽松一些。 - Bryce Siedschlaw

我不太清楚这是关于什么的（不记得我是否曾经需要在堆栈中查找最小值），但是如果您不将重复的最小值添加到S2中，会怎样呢？S2 [321] - Bitterblue

Answer 1

使用链表保存当前最小值。当添加一个新数字时，它会查看先前的最小值，并在当前值较低时将当前最小值更改为当前值。

例如...假设您有数据：3、6、4、2、7、1。那么这就是列表的样子：

value|min

3|3 -> 6|3 -> 4|3 -> 2|2 -> 7|2 -> 1|1

这将会在您推入/弹出项目时跟踪分钟数。当然，您需要有一个根节点和一个被指定为“页脚”的节点，以便您可以在O(1)中访问末尾。

或者您也可以反向操作，将项目添加到前面并在每次插入时更改根节点……那样也可以。它会像这样：

1|1 -> 7|2 -> 2|2 -> 4|3 -> 6|3 -> 3|3

如果这样，您将不需要“footer”节点。

这两个都会跟踪当前最小值，以便在推送值时知道第二个最小值是多少。这样，当实际的最小值被推送时，它将以O(1)的时间知道第二个最小值是什么。

- Bryce Siedschlaw

Answer 2

我在这里发布完整的代码，以便在堆栈中查找最小值和最大值。时间复杂度将为O(1)。

包com.java.util.collection.advance.datastructure;

/** * * 作者：vsinha * */ public abstract interface Stack {

/**
 * 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();

}

包 com.java.util.collection.advance.datastructure;

@SuppressWarnings("hiding") public abstract interface MinMaxStack extends Stack {

public abstract int min();

public abstract int max();

}

包 com.java.util.collection.advance.datastructure;

导入 java.util.Arrays;

/** * * @author vsinha * * @param */ public class MyStack implements Stack {

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 + "]";
}

}

包 com.java.util.collection.advance.datastructure;

/** * 时间复杂度为 O(1)，用于在给定堆栈中查找最小值和最大值。 * 作者 vsinha * */ public class MinMaxStackFinder extends MyStack implements MinMaxStack {

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 + "]" ;
}

}

// 测试程序 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());
}

}

输出：

MyStack [元素=[99, 76, 92, 49, 89, 88, 93, 33, 0, 30], 大小=10, 顶部=9] MinMaxStackFinder [最小栈=MyStack [元素=[99, 76, 49, 33, 0, null, null, null, null, null], 大小=5, 顶部=4] 最大栈=MyStack [元素=[99, null, null, null, null, null, null, null, null, null], 大小=1, 顶部=0]] 最大值：99 最小值：0 MyStack [元素=[99, 76, 92, 49, 89, null, null, null, null, null], 大小=5, 顶部=4] MinMaxStackFinder [最小栈=MyStack [元素=[99, 76, 49, null, null, null, null, null, null, null], 大小=3, 顶部=2] 最大栈=MyStack [元素=[99, null, null, null, null, null, null, null, null, null], 大小=1, 顶部=0]] 最大值：99 最小值：49

如果您有任何问题，请告诉我。

谢谢， VIKASH SINHA

- VIKASH SINHA

Answer 3

这是不可能的。否则，您将能够在线性时间内实现比较排序：首先每个元素都以O（1）的时间推入，总共O（n）的时间，然后n次在O（n）的总时间内获取最小值。

由于已知O（n log n）是比较排序的下限，因此不存在具有O（1）推送和查找最小值的解决方案。

编辑：如Gabe所指出的那样，将“排序”替换为“比较排序”。

- MForster

---

更正：比较排序的时间复杂度不可能优于O(n lg n)。 - Gabe

更具体地说，您可以使用计数排序算法来以O(1)的时间复杂度实现此操作。 - Gabe

请注意，我的答案并不旨在提供完整的数学证明。或者您是在暗示确实存在这样一个栈的O(1)实现吗？ - MForster

我不确定答案，我的分析是你无法获得O(1)的操作，最多只能获得nlog(n)。 - pappu

findmin 不会移除最小值，它只是告诉你最小值是什么。pop 移除的是最新的元素，而不是最小值，因此这些方法不足以实现排序。 - finnw