想追白人本科小妹妹,有什么建议吗? - 未名空间MITBBS历史存档

想追白人本科小妹妹,有什么建议吗?# Love - 情爱幽幽

j*l2010-10-10 07:10

1 楼

中学数学课时候，老师强调过化归的思想，把陌生的题目情景转化为熟悉的题目情景。
面试中也一样。比如下面一道Google名题，后来频频被MSFT, Amazon盗用, 编程之美中
也有
设计一个stack, 使得Push, Pop和GetMin都是O(1)时间
熟悉这题的人都知道，关键是GetMin，为此需要在stack中增加一个下标的链域，通过
它可以得到当前的Min, 至于这个下标链，可以放在分离但并排的辅助stack中，也可以
直接作为stack每个item的数据域之一。
如果面试官这样问：
请你设计一个数据结构，使得插入，删除和GetMin都是O(1)时间，你是否能想到并化归
到上面的名题呢？
如果你从来没有见过和准备到这道名题，你可能会好奇的问面试官，这里头对插入和删
除的位置有什么限定。如果面试官告诉你，你就在一端插入和删除吧。这个无意的解释
实际上就是很明显的提示你用stack了。可惜的是，因为不是你自己想到用stack, 面试官可能就会因为这个间接提示去掉一些credits

r*u2010-10-10 07:10

2 楼

每年一度的亚洲最美女神评选活动终于在昨晚结束了，经过无数亚洲的男女老少痴女傻
男的投票选举后，在无数个参选的美女当众，只能经过无数个人疼割爱的抉择，不知道
要放弃多少美人，最后才能选出是个美女，可谓是千呼万唤始出来
这就是亚洲江湖上的亚洲十美，十大美人，不多说了这美不美的，仁者见仁智者见智，
我绝大多数不敢苟同
十美之中中国的美人占了两席，一个是赵丽颖，一个是郑爽
赵丽颖能上亚洲十美？我真的是无语了，你把俞飞鸿许晴这样的无敌精致大美人放在了
哪里？就算这二位年老色衰了人老珠黄了，不是还有佟丽娅和张歆艺这样的经典的380
度无死角的绝世美女吗？
还有这个什么郑爽，这个郑爽是代表港台地区，可港台区域闭着眼睛看也轮不到郑爽这
样的人，这样的美？真不知道的这种美能代表谁，她只能算好看，要说美从港台地域中
真的也就是中流的水平，再说这不是一个经过生化再造的赝品吗
这个棒子的女娃今年滑落到了第四，记得去年还是第一的位置，我一度怀疑这亚洲十美
的评选只有两个国家参加，其中只有中国，韩国，不然不会这么没有天理，棒子的美女
随便在车站拉出一个来就比这个好看，这人谁？林允儿，好看？好看在哪里？
这个还是棒子的美女，宋智孝，要说这个女孩能上十美，我认为大众的审美还算比较正
常，最起码能代表东方一种含蓄的美，这个我比较同意
算了那几个美还是不要说了，因为真的无法开口，那几个美我认为不能代表亚洲人的最
高审美，而是代表了亚洲人的非正常的重口味，这里面绝对黑幕多多
我直接上十美的第一名，宋慧乔，这个我心服口服

n*g2010-10-10 07:10

3 楼

她现在是我班上的学生,我是她的lab instructor.
现在追肯定违反校规,所以更现实的想法是怎么才能让以后还能继续有机会接触呢？
挺喜欢她的.她学习还挺好,所以也不来office hour,最多在lab的时段内问我.
我立志当个男外f,别鄙视我,确实喜欢白人女生(可能跟小时候父母爱看译制片也带着我
看有关,那时候形成的审美.)

x*32010-10-10 07:10

4 楼

ding

s*u2010-10-10 07:10

5 楼

赵丽颖是个什么鬼？就这柴火妞还亚洲十美？

b*92010-10-10 07:10

6 楼

关键看你最终目标，普通目标，我看就私下解决就可以了。

b*v2010-10-10 07:10

7 楼

赞

【在 j**l 的大作中提到】

: 中学数学课时候，老师强调过化归的思想，把陌生的题目情景转化为熟悉的题目情景。
: 面试中也一样。比如下面一道Google名题，后来频频被MSFT, Amazon盗用, 编程之美中
: 也有
: 设计一个stack, 使得Push, Pop和GetMin都是O(1)时间
: 熟悉这题的人都知道，关键是GetMin，为此需要在stack中增加一个下标的链域，通过
: 它可以得到当前的Min, 至于这个下标链，可以放在分离但并排的辅助stack中，也可以
: 直接作为stack每个item的数据域之一。
: 如果面试官这样问：
: 请你设计一个数据结构，使得插入，删除和GetMin都是O(1)时间，你是否能想到并化归
: 到上面的名题呢？

s*e2010-10-10 07:10

8 楼

380
宋慧乔实至名归，那几个是什么鬼

【在 r*******u 的大作中提到】

: 每年一度的亚洲最美女神评选活动终于在昨晚结束了，经过无数亚洲的男女老少痴女傻
: 男的投票选举后，在无数个参选的美女当众，只能经过无数个人疼割爱的抉择，不知道
: 要放弃多少美人，最后才能选出是个美女，可谓是千呼万唤始出来
: 这就是亚洲江湖上的亚洲十美，十大美人，不多说了这美不美的，仁者见仁智者见智，
: 我绝大多数不敢苟同
: 十美之中中国的美人占了两席，一个是赵丽颖，一个是郑爽
: 赵丽颖能上亚洲十美？我真的是无语了，你把俞飞鸿许晴这样的无敌精致大美人放在了
: 哪里？就算这二位年老色衰了人老珠黄了，不是还有佟丽娅和张歆艺这样的经典的380
: 度无死角的绝世美女吗？
: 还有这个什么郑爽，这个郑爽是代表港台地区，可港台区域闭着眼睛看也轮不到郑爽这

w*r2010-10-10 07:10

9 楼

Sexual harassment。。。

r*o2010-10-10 07:10

10 楼

多谢。
不过请问你怎么用这个下标链在O(1)时间内得到Min呢？

【在 j**l 的大作中提到】

: 中学数学课时候，老师强调过化归的思想，把陌生的题目情景转化为熟悉的题目情景。
: 面试中也一样。比如下面一道Google名题，后来频频被MSFT, Amazon盗用, 编程之美中
: 也有
: 设计一个stack, 使得Push, Pop和GetMin都是O(1)时间
: 熟悉这题的人都知道，关键是GetMin，为此需要在stack中增加一个下标的链域，通过
: 它可以得到当前的Min, 至于这个下标链，可以放在分离但并排的辅助stack中，也可以
: 直接作为stack每个item的数据域之一。
: 如果面试官这样问：
: 请你设计一个数据结构，使得插入，删除和GetMin都是O(1)时间，你是否能想到并化归
: 到上面的名题呢？

r*k2010-10-10 07:10

11 楼

林允儿还是不错的。

w*e2010-10-10 07:10

12 楼

感觉苗头不对，立马勒缰绳，小心她报警。这里不同于中国，千万不要太坚持了。

【在 n******g 的大作中提到】

: 她现在是我班上的学生,我是她的lab instructor.
: 现在追肯定违反校规,所以更现实的想法是怎么才能让以后还能继续有机会接触呢？
: 挺喜欢她的.她学习还挺好,所以也不来office hour,最多在lab的时段内问我.
: 我立志当个男外f,别鄙视我,确实喜欢白人女生(可能跟小时候父母爱看译制片也带着我
: 看有关,那时候形成的审美.)

j*l2010-10-10 07:10

13 楼

每个链，都指向该元素下方（包含该元素)的最小（不一定是全局最小)，这样栈顶的链，一定指向全局的最小。

【在 r****o 的大作中提到】

: 多谢。
: 不过请问你怎么用这个下标链在O(1)时间内得到Min呢？

q*a2010-10-10 07:10

14 楼

这种都比的是人气，而不是比谁真的好看。好看本来就是主观的东西。
人家当红剧女主角不上谁上？

n*g2010-10-10 07:10

15 楼

Thanks for the warning!
I do understand that. That's why I came here asking you guys for "strategy".;

【在 w********e 的大作中提到】

: 感觉苗头不对，立马勒缰绳，小心她报警。这里不同于中国，千万不要太坚持了。

r*o2010-10-10 07:10

16 楼

如果栈顶元素最小，结果把它pop了，那下面所有元素的链怎么更新呢？

【在 j**l 的大作中提到】

: 每个链，都指向该元素下方（包含该元素)的最小（不一定是全局最小)，这样栈顶的链，一定指向全局的最小。

z*w2010-10-10 07:10

17 楼

美不美见仁见智，我还从来没觉得林青霞王祖贤刘嘉玲张曼玉漂亮呢。俞飞鸿从当年演
小李飞刀就不觉得她好看，显老。
觉得人家不漂亮就不漂亮，何必用这么刻薄的言辞。

P*D2010-10-10 07:10

18 楼

我就是进来看有多少人会回帖“外F，死全家”的。不然WSN们也实在是太双重标准了。

j*l2010-10-10 07:10

19 楼

不用更新，请注意我的说法：
每个元素的链，都指向它下方（包含它自身）中的最小元素。

【在 r****o 的大作中提到】

: 如果栈顶元素最小，结果把它pop了，那下面所有元素的链怎么更新呢？

S*g2010-10-10 07:10

20 楼

俞飞鸿太丑了。颧骨突出，又老。

w*e2010-10-10 07:10

21 楼

“外F，死全家”

【在 P****D 的大作中提到】

: 我就是进来看有多少人会回帖“外F，死全家”的。不然WSN们也实在是太双重标准了。

r*o2010-10-10 07:10

22 楼

多谢啊。

【在 j**l 的大作中提到】

: 不用更新，请注意我的说法：
: 每个元素的链，都指向它下方（包含它自身）中的最小元素。

Y*12010-10-10 07:10

23 楼

LZ也po po自己的图吧。哈哈哈

m*n2010-10-10 07:10

24 楼

男女不一样的，百女嫁国男就要融入我中华文化，不像女外F

【在 P****D 的大作中提到】

: 我就是进来看有多少人会回帖“外F，死全家”的。不然WSN们也实在是太双重标准了。

y*i2010-10-10 07:10

25 楼

貌似他假定栈顶是在最上方，下面的元素的链只包含自己下方的元素

【在 r****o 的大作中提到】

: 如果栈顶元素最小，结果把它pop了，那下面所有元素的链怎么更新呢？

p*e2010-10-10 07:10

26 楼

赵丽颖挺好看的

S*U2010-10-10 07:10

27 楼

Talk to her. Find out what she enjoys doing.
Hang out with her if you have a chance, but don't date her yet until you're no longer her instructor.

y*i2010-10-10 07:10

28 楼

问个基本问题，一般面试的时候，这种自己设计的stack内部用什么数据结构呢，链表
还是用标准库的双端队列或其他什么的？

【在 j**l 的大作中提到】

: 中学数学课时候，老师强调过化归的思想，把陌生的题目情景转化为熟悉的题目情景。
: 面试中也一样。比如下面一道Google名题，后来频频被MSFT, Amazon盗用, 编程之美中
: 也有
: 设计一个stack, 使得Push, Pop和GetMin都是O(1)时间
: 熟悉这题的人都知道，关键是GetMin，为此需要在stack中增加一个下标的链域，通过
: 它可以得到当前的Min, 至于这个下标链，可以放在分离但并排的辅助stack中，也可以
: 直接作为stack每个item的数据域之一。
: 如果面试官这样问：
: 请你设计一个数据结构，使得插入，删除和GetMin都是O(1)时间，你是否能想到并化归
: 到上面的名题呢？

m*a2010-10-10 07:10

29 楼

380
淡淡妞应该上自己的图，那绝对碾压宋慧乔的

【在 r*******u 的大作中提到】

: 每年一度的亚洲最美女神评选活动终于在昨晚结束了，经过无数亚洲的男女老少痴女傻
: 男的投票选举后，在无数个参选的美女当众，只能经过无数个人疼割爱的抉择，不知道
: 要放弃多少美人，最后才能选出是个美女，可谓是千呼万唤始出来
: 这就是亚洲江湖上的亚洲十美，十大美人，不多说了这美不美的，仁者见仁智者见智，
: 我绝大多数不敢苟同
: 十美之中中国的美人占了两席，一个是赵丽颖，一个是郑爽
: 赵丽颖能上亚洲十美？我真的是无语了，你把俞飞鸿许晴这样的无敌精致大美人放在了
: 哪里？就算这二位年老色衰了人老珠黄了，不是还有佟丽娅和张歆艺这样的经典的380
: 度无死角的绝世美女吗？
: 还有这个什么郑爽，这个郑爽是代表港台地区，可港台区域闭着眼睛看也轮不到郑爽这

w*12010-10-10 07:10

30 楼

这么说，链接指向的数据，其实是相当于排过序的了
第一个LINK 指向全局最先，第二个指向第二小。。。。

链，一定指向全局的最小。

【在 j**l 的大作中提到】

: 每个链，都指向该元素下方（包含该元素)的最小（不一定是全局最小)，这样栈顶的链，一定指向全局的最小。

m*k2010-10-10 07:10

31 楼

什么审美，赵丽颖好看，还有么有天理，还有那个香港那个什么郑爽？郭采洁多好的闺
女，强她一万倍

【在 p*****e 的大作中提到】

: 赵丽颖挺好看的

b*h2010-10-10 07:10

32 楼

那一次GetMin()之后，是不是所有的链都要更新那？如果这样的话，GetMin就不是O（1
）了。
比如我push 1 - 10, 然后连续调用getmin。每个getmin都要update n个链。复杂度就
是O（n）了。

链，一定指向全局的最小。

【在 j**l 的大作中提到】

: 每个链，都指向该元素下方（包含该元素)的最小（不一定是全局最小)，这样栈顶的链，一定指向全局的最小。

c*a2010-10-10 07:10

33 楼

好的没申请，当然就不能选上了。申请的都是想通过这个走红的，也就是说还不红，活
着不是很红的。

j*l2010-10-10 07:10

34 楼

不需要更新。每当一个元素成为当前的栈顶元素，它的链域指向的一定是全局的最小。
当一个元素还不是栈顶元素的时候，它的链域指向的是它下方的所有元素(括它自己)中
的最小，但全局最小可能在它上方。

（1

【在 b********h 的大作中提到】

: 那一次GetMin()之后，是不是所有的链都要更新那？如果这样的话，GetMin就不是O（1
: ）了。
: 比如我push 1 - 10, 然后连续调用getmin。每个getmin都要update n个链。复杂度就
: 是O（n）了。
:
: 链，一定指向全局的最小。

n*g2010-10-10 07:10

35 楼

唉可怜。

380

【在 r*******u 的大作中提到】

: 每年一度的亚洲最美女神评选活动终于在昨晚结束了，经过无数亚洲的男女老少痴女傻
: 男的投票选举后，在无数个参选的美女当众，只能经过无数个人疼割爱的抉择，不知道
: 要放弃多少美人，最后才能选出是个美女，可谓是千呼万唤始出来
: 这就是亚洲江湖上的亚洲十美，十大美人，不多说了这美不美的，仁者见仁智者见智，
: 我绝大多数不敢苟同
: 十美之中中国的美人占了两席，一个是赵丽颖，一个是郑爽
: 赵丽颖能上亚洲十美？我真的是无语了，你把俞飞鸿许晴这样的无敌精致大美人放在了
: 哪里？就算这二位年老色衰了人老珠黄了，不是还有佟丽娅和张歆艺这样的经典的380
: 度无死角的绝世美女吗？
: 还有这个什么郑爽，这个郑爽是代表港台地区，可港台区域闭着眼睛看也轮不到郑爽这

j*l2010-10-10 07:10

36 楼

你有调用Pop么？每个getmin，都是返回栈顶元素的链指向的那个元素
Push 1- 10 后的情形
stack元素序号元素值链域
9 10 0
8 9 0
7 8 0
6 7 0
5 6 0
4 5 0
3 4 0
2 3 0
1 2 0
0 1 0

（1

【在 b********h 的大作中提到】

: 那一次GetMin()之后，是不是所有的链都要更新那？如果这样的话，GetMin就不是O（1
: ）了。
: 比如我push 1 - 10, 然后连续调用getmin。每个getmin都要update n个链。复杂度就
: 是O（n）了。
:
: 链，一定指向全局的最小。

r*12010-10-10 07:10

37 楼

我觉得赵丽颖很有灵气，水灵，比第一名宋慧乔漂亮，后者看起来木木的。

b*h2010-10-10 07:10

38 楼

我懂你的意思。我的意思是说你getmin之后，这个min要不要从堆栈中删除？一旦删除
，所有的链都有可能不准确了。这样必然要更新一次。
当然，如果不需要删除，就不需要更新了。但这样这个getmin连续多次调用的结果都是
一样的。似乎不怎么自然。

【在 j**l 的大作中提到】

: 不需要更新。每当一个元素成为当前的栈顶元素，它的链域指向的一定是全局的最小。
: 当一个元素还不是栈顶元素的时候，它的链域指向的是它下方的所有元素(括它自己)中
: 的最小，但全局最小可能在它上方。
:
: （1

M*i2010-10-10 07:10

39 楼

挺好

b*h2010-10-10 07:10

40 楼

不pop，就getmin。

【在 j**l 的大作中提到】

: 你有调用Pop么？每个getmin，都是返回栈顶元素的链指向的那个元素
: Push 1- 10 后的情形
: stack元素序号元素值链域
: 9 10 0
: 8 9 0
: 7 8 0
: 6 7 0
: 5 6 0
: 4 5 0
: 3 4 0

f*e2010-10-10 07:10

41 楼

这是什么鬼活动？郑爽什么时候成了港台地区的了？
俞飞鸿是无敌精致大美人？笑死人！
佟丽娅哪里无死角了，牙齿就是她的死角。皮肤也不好，不ps不能见光。
张歆艺和赵丽颖是两种气质的美。
棒子就不用说了，没有一个比得上赵丽颖的。

380

【在 r*******u 的大作中提到】

: 每年一度的亚洲最美女神评选活动终于在昨晚结束了，经过无数亚洲的男女老少痴女傻
: 男的投票选举后，在无数个参选的美女当众，只能经过无数个人疼割爱的抉择，不知道
: 要放弃多少美人，最后才能选出是个美女，可谓是千呼万唤始出来
: 这就是亚洲江湖上的亚洲十美，十大美人，不多说了这美不美的，仁者见仁智者见智，
: 我绝大多数不敢苟同
: 十美之中中国的美人占了两席，一个是赵丽颖，一个是郑爽
: 赵丽颖能上亚洲十美？我真的是无语了，你把俞飞鸿许晴这样的无敌精致大美人放在了
: 哪里？就算这二位年老色衰了人老珠黄了，不是还有佟丽娅和张歆艺这样的经典的380
: 度无死角的绝世美女吗？
: 还有这个什么郑爽，这个郑爽是代表港台地区，可港台区域闭着眼睛看也轮不到郑爽这

j*l2010-10-10 07:10

42 楼

题目的意思，GetMin就和GetTop一样，是只读操作，不像Push, Pop一样会改变栈。

【在 b********h 的大作中提到】

: 不pop，就getmin。

q*82010-10-10 07:10

43 楼

我觉得赵丽蓉最好看

【在 r********1 的大作中提到】

: 我觉得赵丽颖很有灵气，水灵，比第一名宋慧乔漂亮，后者看起来木木的。

j*l2010-10-10 07:10

44 楼

如果你不Push新的元素或者Pop已有的元素，连续调用GetMin当然返回同一个值。这道
题主要就是考查如果有更小的元素Push进来，或者当前最小的元素被Pop，如何还能正
确返回min。

【在 b********h 的大作中提到】

: 我懂你的意思。我的意思是说你getmin之后，这个min要不要从堆栈中删除？一旦删除
: ，所有的链都有可能不准确了。这样必然要更新一次。
: 当然，如果不需要删除，就不需要更新了。但这样这个getmin连续多次调用的结果都是
: 一样的。似乎不怎么自然。

a*n2010-10-10 07:10

45 楼

觉得郑爽比郭采洁好看多了，郭采洁在明星里相貌也就中等吧

【在 m****k 的大作中提到】

:
: 什么审美，赵丽颖好看，还有么有天理，还有那个香港那个什么郑爽？郭采洁多好的闺
: 女，强她一万倍

B*t2010-10-10 07:10

46 楼

空间利用率不是很好，试想如果stack中push了10^6个数，最先push进去的数恰好又是
这10^6个数中最小的，你那个10^6大小的链域岂不是太浪费空间了？

美中
以
归

【在 j**l 的大作中提到】

: 中学数学课时候，老师强调过化归的思想，把陌生的题目情景转化为熟悉的题目情景。
: 面试中也一样。比如下面一道Google名题，后来频频被MSFT, Amazon盗用, 编程之美中
: 也有
: 设计一个stack, 使得Push, Pop和GetMin都是O(1)时间
: 熟悉这题的人都知道，关键是GetMin，为此需要在stack中增加一个下标的链域，通过
: 它可以得到当前的Min, 至于这个下标链，可以放在分离但并排的辅助stack中，也可以
: 直接作为stack每个item的数据域之一。
: 如果面试官这样问：
: 请你设计一个数据结构，使得插入，删除和GetMin都是O(1)时间，你是否能想到并化归
: 到上面的名题呢？

r*n2010-10-10 07:10

47 楼

演员是被选中的必要条件吗？
美人为什么不长奶？

380

【在 r*******u 的大作中提到】

: 每年一度的亚洲最美女神评选活动终于在昨晚结束了，经过无数亚洲的男女老少痴女傻
: 男的投票选举后，在无数个参选的美女当众，只能经过无数个人疼割爱的抉择，不知道
: 要放弃多少美人，最后才能选出是个美女，可谓是千呼万唤始出来
: 这就是亚洲江湖上的亚洲十美，十大美人，不多说了这美不美的，仁者见仁智者见智，
: 我绝大多数不敢苟同
: 十美之中中国的美人占了两席，一个是赵丽颖，一个是郑爽
: 赵丽颖能上亚洲十美？我真的是无语了，你把俞飞鸿许晴这样的无敌精致大美人放在了
: 哪里？就算这二位年老色衰了人老珠黄了，不是还有佟丽娅和张歆艺这样的经典的380
: 度无死角的绝世美女吗？
: 还有这个什么郑爽，这个郑爽是代表港台地区，可港台区域闭着眼睛看也轮不到郑爽这

j*l2010-10-10 07:10

48 楼

可以这样解决的，栈的class附加一个变量min_id, 保存当前最小的min元素的下标, 只
有push进来更小的数，才会去更新min_id, 旧的min_id序列依次保存在栈内的一个
vector里头，最新的min_id在vector的末尾。当pop一个元素时候，如果它的下标等于
vector末尾元素的值，则对vector进行pop_back操作，同时更新min_id(次小)。GetMin就是取当前的min_id，用它作下标返回栈元素值。
对你这种情况，vector的大小就是1
实际上变量min_id也不是必需的，它就是vector的末尾元素，只需要维护那个vector就可以了

【在 B*****t 的大作中提到】

: 空间利用率不是很好，试想如果stack中push了10^6个数，最先push进去的数恰好又是
: 这10^6个数中最小的，你那个10^6大小的链域岂不是太浪费空间了？
:
: 美中
: 以
: 归

B*t2010-10-10 07:10

49 楼

变量min_id没有必要。用一个单调递减的stack，stack的top保存min元素的下标。

只
于
GetMin就是取当前的min_id，用它作下标返回栈元素值。

【在 j**l 的大作中提到】

: 可以这样解决的，栈的class附加一个变量min_id, 保存当前最小的min元素的下标, 只
: 有push进来更小的数，才会去更新min_id, 旧的min_id序列依次保存在栈内的一个
: vector里头，最新的min_id在vector的末尾。当pop一个元素时候，如果它的下标等于
: vector末尾元素的值，则对vector进行pop_back操作，同时更新min_id(次小)。GetMin就是取当前的min_id，用它作下标返回栈元素值。
: 对你这种情况，vector的大小就是1
: 实际上变量min_id也不是必需的，它就是vector的末尾元素，只需要维护那个vector就可以了

r*o2010-10-10 07:10

50 楼

你说的当前的min_id就是末尾的min_id吗？
不过这样是不是也有问题，如果跟刚才那个例子相反，每次加入的元素都比前一个小，
这样加入10^6个元素的话，vector的size也很客观啊。

GetMin就是取当前的min_id，用它作下标返回栈元素值。
就可以了

【在 j**l 的大作中提到】

: 可以这样解决的，栈的class附加一个变量min_id, 保存当前最小的min元素的下标, 只
: 有push进来更小的数，才会去更新min_id, 旧的min_id序列依次保存在栈内的一个
: vector里头，最新的min_id在vector的末尾。当pop一个元素时候，如果它的下标等于
: vector末尾元素的值，则对vector进行pop_back操作，同时更新min_id(次小)。GetMin就是取当前的min_id，用它作下标返回栈元素值。
: 对你这种情况，vector的大小就是1
: 实际上变量min_id也不是必需的，它就是vector的末尾元素，只需要维护那个vector就可以了

j*l2010-10-10 07:10

51 楼

最坏情况下是这样的。

【在 r****o 的大作中提到】

: 你说的当前的min_id就是末尾的min_id吗？
: 不过这样是不是也有问题，如果跟刚才那个例子相反，每次加入的元素都比前一个小，
: 这样加入10^6个元素的话，vector的size也很客观啊。
:
: GetMin就是取当前的min_id，用它作下标返回栈元素值。
: 就可以了

j*l2010-10-10 07:10

52 楼

我说的那个vector, 和你说的这个单调递减的辅助stack是类似的。考虑到STL对vector
进行push_back操作时候，可能会有重新申请新的空间，复制元素这样的线性额外开销
。题目要求Push操作也是O(1), 而Push会引起vector的push_back。所以你说的这个
stack更好，当然要用链表来实现，这样就可以按需增长，也没有vector的那种线性开
销。

【在 B*****t 的大作中提到】

: 变量min_id没有必要。用一个单调递减的stack，stack的top保存min元素的下标。
:
: 只
: 于
: GetMin就是取当前的min_id，用它作下标返回栈元素值。

r*o2010-10-10 07:10

53 楼

看来没有什么最好的方案啊。

【在 j**l 的大作中提到】

: 最坏情况下是这样的。

j*l2010-10-10 07:10

54 楼

空间换时间，要使得栈在任何时刻都可以有O(1)的GetMin操作，总要付出一定的空间代
价吧。

【在 r****o 的大作中提到】

: 看来没有什么最好的方案啊。