跳转到指定楼层
上一主题 下一主题
收起左侧

L家一道题max Stack 要求全部O(1) 看看我的解答对吗

🔗
 楼主| 我一辈子赖美帝 2017-10-16 06:56:59 | 只看该作者
全局:
yesterdaysea 发表于 2017-10-16 06:55
你的popmax()是O(n). 1) java pq remove() 是O(n). 2) linkedList remove() 也是O(n).

ye ,那个版本全是错的,时间复杂度达不到要求。连lg n 都达不到。
回复

使用道具 举报

🔗
yesterdaysea 2017-10-16 06:59:36 | 只看该作者
全局:
第二个版本function不对。应该不work。只update了maxStack. 没有update valuestack. 如果要update valuestack, 你这个做法也是O(n).
回复

使用道具 举报

🔗
ivanyang 2017-10-16 07:00:55 | 只看该作者
全局:
我一辈子赖美帝 发表于 2017-10-16 06:56
ye ,那个版本全是错的,时间复杂度达不到要求。连lg n 都达不到。

我的思路是这样的:
std::list<int> stack;
std::list<std::list<int>::iterator> maxStack;
这样其他的没啥问题,popMax 的直接stack.erase(maxStack.back()), maxStack.pop()就行了。
回复

使用道具 举报

🔗
jessebest 2017-10-16 07:01:16 | 只看该作者
全局:
楼主是全职还是实习啊
回复

使用道具 举报

🔗
 楼主| 我一辈子赖美帝 2017-10-16 07:03:12 | 只看该作者
全局:
ivanyang 发表于 2017-10-16 06:53
LZ有网上答案的link吗?能分享一下吗?非常感谢。

这就是我抄的Link.  http://wxx5433.github.io/max-stack.html
不过忽然发现人没错,人没说让所有操作O1.
回复

使用道具 举报

🔗
 楼主| 我一辈子赖美帝 2017-10-16 07:03:55 | 只看该作者
全局:
求哪位大神贴一个所有操作O1的code?
回复

使用道具 举报

🔗
 楼主| 我一辈子赖美帝 2017-10-16 07:07:28 | 只看该作者
全局:
jessebest 发表于 2017-10-16 07:01
楼主是全职还是实习啊

明天onsite,全职
回复

使用道具 举报

🔗
 楼主| 我一辈子赖美帝 2017-10-16 07:14:01 | 只看该作者
全局:
到此为止咯,我就准备第二版那个答案了。
加一个valueStack.remove(maxStack.peek());
回复

使用道具 举报

🔗
wtcupup 2017-10-16 07:32:05 | 只看该作者
全局:
本帖最后由 wtcupup 于 2017-10-16 07:40 编辑
我一辈子赖美帝 发表于 2017-10-16 07:14
到此为止咯,我就准备第二版那个答案了。
加一个valueStack.remove(maxStack.peek());

在哪个function里加这一行?
ignore my reply
回复

使用道具 举报

🔗
heroic 2017-10-16 07:37:59 | 只看该作者
全局:
没有所有操作的O(1)解。否则你把乱序的n个元素的数组push进去 不停的运行popmax() n次得到一个有序数组。这样可以实现O(n)的排序 这是不可能的
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表