在 O(1) 中实现堆栈（push、pop 和 findmin）

Question

我已经看过这个问题的两个堆栈实现，但我真的很困惑如何获得 O(1) 操作。 考虑以下示例：

S1[3542761986759]
S2[3332221111111]

这里的想法/算法是

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

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

谁能帮我理解解决方案吗？

Answer 1

这是不可能的。否则，您将能够在线性时间内实现比较排序：首先在 O(1) 时间内推送所有元素，总时间为 O(n)，然后 n 次在 O(n) 总时间内获得最小值。

众所周知，O(n log n) 是比较排序的下限，因此具有 O(1) push 和 findmin 的解决方案不存在。

编辑：如 Gabe 所说，将“排序”替换为“比较排序”。

Answer 2

我在这里发布完整的代码，以在堆栈中查找 min 和 mx 。
时间复杂度为 O(1)

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

/**
*
*@作者vsinha
*
*/
公共抽象接口堆栈{

/**
 * 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.datastruct;

@SuppressWarnings(“隐藏”)
公共抽象接口 MinMaxStack 扩展了 Stack {

public abstract int min();

public abstract int max();

}

package com.java.util.collection.advance.datastruct;

导入java.util.Arrays；

/**
*
*@作者vsinha
*
* @参数
*/
公共类 MyStack 实现 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.datastruct;

/**
* 在给定堆栈中查找最小值和最大值的时间复杂度为 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 + "]" ;
}

}

// 测试程序

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

导入 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 [elements=[99, 76, 92, 49, 89, 88, 93, 33, 0, 30], size=10, top=9]
MinMaxStackFinder [minStack=MyStack [元素=[99, 76, 49, 33, 0, null, null, null, null, null], size=5, top=4]
maxStack=MyStack [元素=[99, null, null, null, null, null, null, null, null, null], size=1, top=0]]
最大：99
最小值：0
MyStack [元素=[99, 76, 92, 49, 89, null, null, null, null, null], size=5, top=4]
MinMaxStackFinder [minStack=MyStack [元素=[99, 76, 49, null, null, null, null, null, null, null], size=3, top=2]
maxStack=MyStack [元素=[99, null, null, null, null, null, null, null, null, null], size=1, top=0]]
最大：99
分钟：49

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

谢谢，
维卡什·辛哈

Answer 3

使用链表存储当前最小值。当您添加新数字时，它会查看前一个最小值，如果当前值较低，则将当前最小值更改为当前值。

例如.. 假设您有数据：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

那么你就不需要“页脚”节点。

这两者都会跟踪推送值时的当前最小值。这样，当推送实际最小值时，它将知道 O(1) 中的第二个最小值是多少。