java - 以这样的方式实现堆栈，以便我们可以在 O(1) 中找到最小值

Question

面试问题:我们想要找出堆栈中的最小元素。因此，以这样的方式实现堆栈，它将在 O(1) 的任何时间点为我提供最小元素还有一个条件，寻找最小元素的空间复杂度应该是O(1)

时间复杂度:

推送操作:O(1)

弹出操作:O(1)

获取最小元素:O(1)

如何做到这一点？

例如，推(2);

堆栈:

2 <- 顶部

最小值:2

推(3);

堆栈:

3 <- 顶部

2

最小值:2

推(1);

堆栈:

1 <- 顶部

3

2

最小值:1

弹出();

堆栈:

3 <- 顶部

2

最少:2

Answer 1

正如其他人所提到的，空间复杂度本质上是O(n)，但是对这样的问题的一个简单答案就是让push和pop做更多的工作并且做得更多效率比平时低。

因此，您将一个 int minVal 添加到堆栈中，然后每次压入或弹出时，只需更新相对于压入和弹出的值即可。因此，如果最小值为 1 并且弹出 1，那么我们会再次在整个堆栈中寻找最小值。如果我们压入 0，但我们的最小值当前为 1，则同样如此，我们将最小值设置为 0。

这使得 getMin() O(1) 但其他函数效率较低 - 这仍然符合问题的规则。

当然有更好的方法来最小化对push/pop的影响，但它会炸毁空间。