java - java维护栈的算法

<分区>

您将如何维护一个堆栈，以便无论何时从堆栈中弹出，您都知道堆栈中的最小元素？该算法应该具有恒定的复杂度

提前致谢

最佳答案

好的，这是你需要做的......

您需要维护一些数据结构，其中包含您插入的每个元素的信息，最小值 和第二个最小值 值是多少插入该元素的时间..

所以，你想要这样的信息:-

对于每个推送的元素 ->

当您从堆栈中弹出该元素时，将需要此信息。因此，无论您是否弹出最小值，您都会知道。如果是, 那么你可以在推送这个元素之前用 minimum 替换当前的 minimum 值。如果不是，那么 minimum 将不会发生变化> 当时的值(value)..

例如:-

假设当前堆栈中有以下元素:-

[3, 5, 7, 9, 2, 4]

然后你推送一个值 8.. 然后你有两个值要维护.. (pushed中8之前的最小值，即2，8之后的minimum值被插入，即 2): -
```
min_value_before_push = min(stack)
push 8
min_value_after_push = min(stack)
```
如果您压入一个值 1，则 minimum_before_insertion 为 2，和 minimum_after_insertion 是 1: -
```
min_value_before_push = 2
min_value_after_push = 1
```

现在你的堆栈是:-

[1, 8, 3, 5, 7, 9, 2, 4]

现在，如果您pop，您将看到value 1:-

    min_value_before_push = 2
    min_value_after_push = 1

因此，弹出将改变最小值，因此，您将 minimum_value_before_push 更改为 1.. 因此，您的最小值再次为 2..

您当前的堆栈变为:-

[8, 3, 5, 7, 9, 2, 4]

现在，让我们检查一下这个算法是否适用于 duplicate 元素:-

假设你想再次压入一个value 2..

min_value_before_push = 2
min_value_after_push = 2

然后你继续 pop，你会看到对于 value 2，min_value_after_push 是 2，所以这意味着弹出它会改变最小值.. 所以你用 min_value_before_push 替换这个值，它也是 2.. 这正是我们想要的..

注意:- 该算法的一个好处是，您无需进行太多比较。只需在推送时与 current_minimum_value 进行比较即可。当您pop..

时与current_minimum_value 进行比较

你可以试着继续思考你可以拥有什么样的数据结构..

关于java - java维护栈的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12634574/