|
锁定老帖子 主题：百度一面算法题(常数时间内求栈中最大值)
精华帖 (0) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-11-13
nicholas.sun 写道 忍不住问一下这题意义何在？
不然，EldonReturn的方法已经可以了 更夸张点，每次操作的时候把比较得出的最大值单独保存起来也可以 呵呵，这样虽然不是求栈中最大值了 但楼主的场景又是怎么样的呢？ 这题就是为了考你怎么用空间换时间。 EldonReturn的方法确实是已经实现的。 每次操作的时候把比较得出的最大值单独保存在一个栈中也可以实现。 不太懂，你问我的场景是什么的意思。。。 |
| 返回顶楼 | |
|
发表时间：2011-11-16
yeshaoting 写道
算法描述： 一个栈stack，具有push和pop操作，其时间复杂度皆为O(1)。 设计算法max操作，求栈中的最大值，该操作的时间复杂度也要求为O(1)。 可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间复杂度，空间时间复杂度无要求。 思路： 我借助一个变量count和一个数组空间（其实就是一个栈）完成该时间复杂度为O(1)的算法设计。
不用太复杂，只是求栈中的最大值，增加一个变量，保存最大值Max,然后在push中比较后更新最大值就可以了。 |
| 返回顶楼 | |
|
发表时间：2011-11-16
youtops 写道
yeshaoting 写道
算法描述： 一个栈stack，具有push和pop操作，其时间复杂度皆为O(1)。 设计算法max操作，求栈中的最大值，该操作的时间复杂度也要求为O(1)。 可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间复杂度，空间时间复杂度无要求。 思路： 我借助一个变量count和一个数组空间（其实就是一个栈）完成该时间复杂度为O(1)的算法设计。
不用太复杂，只是求栈中的最大值，增加一个变量，保存最大值Max,然后在push中比较后更新最大值就可以了。
这是在push与pop操作都会随机出现的场景. 出现pop操作,一个变量是搞不定的. |
| 返回顶楼 | |
|
发表时间：2011-11-16
只要修改栈的存储方式就可以了！！存储的时候总把最大的值放在栈顶！！
|
| 返回顶楼 | |
|
发表时间：2011-11-16
wowo12345 写道 只要修改栈的存储方式就可以了！！存储的时候总把最大的值放在栈顶！！
你把栈改成排序树了 |
| 返回顶楼 | |
|
发表时间：2011-12-16
用个辅助栈 存放最大值，每次比较之后在入
最后取得时候 直接栈顶出栈 |
| 返回顶楼 | |
|
发表时间：2011-12-28
严格地说，pop和push都是O(1)时间，而找出最大最小值，就是要对栈元素排序，对于n个元素入栈，在n*O(1)个时间即O(n)内完成排序是不可能的。所以，上述的程序肯定都有问题。
|
| 返回顶楼 | |
|
发表时间：2011-12-28
之前分析有错误，重新分析一下，针对栈里每个元素，该元素之前的最大最小值是一定的，所以新加入元素只需和上一元素对应的最大最小值比即可。不涉及排序，因此是O(1)复杂度的。
|
| 返回顶楼 | |
|
发表时间：2011-12-28
EldonReturn 写道 想了个猥琐的方法。空间开销大点。
class StackElement { int value; int maxValue; }; 每次压栈的时候，比较一下栈顶元素的maxValue和自己当前元素的值，最大的那个写到当前元素的maxValue里面去。 跟我的想法一样，大意就是这样，估计唯一的方法了 |
| 返回顶楼 | |
|
发表时间：2012-02-04
最后修改：2012-02-04
保存一个最大值就行了吧，直接返回该值
并未说能pop出最大值的时间是o(1)吧！ |
| 返回顶楼 | |
