在O(1)时间复杂度下获取栈中的最小元素

Question

我提出这个问题的原因是因为我不明白为什么我所想到的方法不能应用于这个特定的问题。

我的基本解决方案：如果我们在 stack 类中有一个变量，每当我们将一个项目推入栈时，我们会检查它是否 小于 我们的 min 变量。如果是，则将值分配给最小值，否则忽略。

您仍将获得 O(1)，因为 min 函数将会；

int getMinimum(){
  return min;
}

为什么从来没有人提到这个解决方案，或者我思考的方式有什么问题？

- Ali

---

如果从栈中弹出了最小元素，你如何在O(1)时间内找到新的最小值？ - Sebastian Paaske Tørholm

@SebastianPaaskeTørholm 非常感谢。我现在明白了。 - Ali

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

Answer 1

如果您从堆栈中弹出数字，则此方法将无法运行。

例如：2、4、5、3、1。当您弹出1后，最小值是多少？

解决方案是保持最小值的堆栈，而不仅仅是一个单独的值。如果您遇到一个小于等于当前最小值的值，则需要将其推入最小堆栈。

例如：

Push(4):
Stack: 4
Min-stack: 4

Push(2):
Stack: 4 2
Min-stack: 4 2

Push(2):
Stack: 4 2 2
Min-stack: 4 2 2

Push(5):
Stack: 4 2 2 5
Min-stack: 4 2 2

Push(3):
Stack: 4 2 2 5 3
Min-stack: 4 2 2

Push(1):
Stack: 4 2 2 5 3 1
Min-stack: 4 2 2 1

Pop():
Stack: 4 2 2 5 3
Min-stack: 4 2 2

Pop():
Stack: 4 2 2 5
Min-stack: 4 2 2

Pop():
Stack: 4 2 2
Min-stack: 4 2 2

Pop():
Stack: 4 2
Min-stack: 4 2

Pop():
Stack: 4
Min-stack: 4

- Steven Liao

---

非常感谢！终于明白了。 - Ali

当然，在时间结束后:D - Ali

你需要将相等的元素也推入最小堆栈。我不确定你是否有意这样做，但应该明确提到。 - Daniel Fischer

好的，我想让我的例子简洁明了，但我会加上它。 - Steven Liao

Answer 2

使用链表来跟踪最小值，它将成为头部。请注意，linkedlist.app = append（我们将值放在尾部）。linkedlist.pre = prepend（我们将值作为链表的头部）。

公共类堆栈 {

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

}

}

- Zok

Answer 3

我在这里找到了解决方案here

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;
};

- isxaker