从堆栈最小值 [英] Min Value from Stack

查看:277
本文介绍了从堆栈最小值的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一个堆栈,其中包含一些整型数据。我想了解从堆栈的最小值为O(1)时间。你知道吗?

I have a stack which contains some integer data. I want to find out the min value from Stack in O(1) time. Any idea?

PS:有没有订货数据的堆栈(增加/减少)

PS: There is no ordering (increasing/decreasing) of data in Stack.

谢谢

纳文

推荐答案

使用两个堆栈。一个是数据,一个是最低要求。当你推到数据栈,推新最低到最低栈(新的最小是你推项目的分,无论是目前的最低的栈顶),而当你弹出,弹出关闭两个堆栈的(使得两个堆栈始终具有相同的元素数)。要找到的最小元素,只看最低堆栈的顶部。

Use two stacks. One is the data, one is the minimums. When you push onto the data stack, push the new minimum onto the minimums stack (the new minimum is the min of the item you're pushing and whatever is currently on the top of the minimums stack), and when you pop, pop off of both stacks (so that the two stacks always have the same number of elements). To find the minimum element, just look at the top of the minimums stack.

推,弹出并找到最小值为O(1)。

Pushing, popping and finding the min value are O(1).

这篇关于从堆栈最小值的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆