Nav*_*een 6 c algorithm data-structures
我有一个包含一些整数数据的堆栈.我想在O(1)时间内找出Stack中的最小值.任何的想法？
PS:Stack中没有数据的排序(增加/减少).
谢谢,
纳文
ESR*_*ogs 28
使用两个堆栈.一个是数据,一个是最小值.当您按下数据堆栈时,将新的最小值推到最小堆栈上(新的最小值是您正在推送的项目的最小值以及当前位于最小值堆栈顶部的任何内容),当您弹出时,弹出两个堆栈(以便两个堆栈始终具有相同数量的元素).要查找最小元素,只需查看最小堆栈的顶部.
推送,弹出和找到最小值是O(1).