|
锁定老帖子 主题：百度一面算法题(常数时间内求栈中最大值)
精华帖 (0) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-11-08
297014031 写道 做一链状列表；
push的时候 链表插入元素，并保持链表降序排列； pup的时候直接在链表种找到结点删除即可。 链表第一个结点始终为栈中元素最大值。 如何控制链表降序排序的时间复杂度为O(1)? |
| 返回顶楼 | |
|
发表时间：2011-11-08
想了个猥琐的方法。空间开销大点。
class StackElement { int value; int maxValue; }; 每次压栈的时候，比较一下栈顶元素的maxValue和自己当前元素的值，最大的那个写到当前元素的maxValue里面去。 |
| 返回顶楼 | |
|
发表时间：2011-11-08
最后修改：2011-11-08
EldonReturn 写道 想了个猥琐的方法。空间开销大点。
class StackElement { int value; int maxValue; }; 每次压栈的时候，比较一下栈顶元素的maxValue和自己当前元素的值，最大的那个写到当前元素的maxValue里面去。 和2楼的方法没有本质区别 解法的关键是：对于每一个栈状态，都冗余存储一个相应的maxValue值，push时只需要与上个栈状态的maxValue值比较就可以得到新栈状态的maxValue值，所以时间复杂度为O(1) 空间复杂度为2n 2楼的代码，“噪声”太多，排版又不好，可读性也就差了。。 |
| 返回顶楼 | |
|
发表时间：2011-11-09
yeshaoting 写道 tswwz 写道 可以考虑与当前stack维护对应的代表stack对应位置的最大值的栈MaxStack
对于栈stack push元素 valueA时 maxValue = popMaxStack(); pushMaxStack(maxValue); if (valueA >= maxValue) pushStack(valueA) ; pushMaxStack(valueA); if (valueA < maxValue) pushStack(valueA) ; pushMaxStack(maxValue); pop元素 maxValue = popMaxStack(); pushMaxStack(maxValue); valueA = popStack(); popMaxStack(); 这样取最大值时，直接 maxValue = popMaxStack();pushMaxStack(maxValue);就ok了。 确实是有额外用到一个栈空间. 我的push元素想法跟你一样. 但是没太看懂你的pop元素. 他的pop其实就是popMaxStack();至于maxValue = popMaxStack(); pushMaxStack(maxValue);起到的作用就是获取栈顶元素。。。所以其实简单点写 pop元素 maxValue = popMaxStack(); valueA = popStack(); 就ok啦。。。 |
| 返回顶楼 | |
|
发表时间：2011-11-10
不仅空间换时间，时间转移到push中了吧
|
| 返回顶楼 | |
|
发表时间：2011-11-10
red_xie 写道 不仅空间换时间，时间转移到push中了吧
都O(1)的时间,不必计较时间转移到那儿了吧? 可以修改push,也可以不在push基础上修改.都能实现的~ |
| 返回顶楼 | |
|
发表时间：2011-11-10
EldonReturn 写道 想了个猥琐的方法。空间开销大点。
class StackElement { int value; int maxValue; }; 每次压栈的时候，比较一下栈顶元素的maxValue和自己当前元素的值，最大的那个写到当前元素的maxValue里面去。 这种方法把二个独立的栈合并到了一起~~ 
|
| 返回顶楼 | |
|
发表时间：2011-11-11
PUSH的时候计算最大值存起来。
|
| 返回顶楼 | |
|
发表时间：2011-11-11
补充一个，可以改变push 和 pop的存储方式是不是就意味可以使用类似 优先队列的方式来实现一个“优先栈”？
|
| 返回顶楼 | |
|
发表时间：2011-11-13
忍不住问一下这题意义何在？
不然，EldonReturn的方法已经可以了 更夸张点，每次操作的时候把比较得出的最大值单独保存起来也可以 呵呵，这样虽然不是求栈中最大值了 但楼主的场景又是怎么样的呢？ |
| 返回顶楼 | |
