j**l
发帖数: 2911 | 1 中学数学课时候，老师强调过化归的思想，把陌生的题目情景转化为熟悉的题目情景。
面试中也一样。比如下面一道Google名题，后来频频被MSFT, Amazon盗用, 编程之美中
也有
设计一个stack, 使得Push, Pop和GetMin都是O(1)时间
熟悉这题的人都知道，关键是GetMin，为此需要在stack中增加一个下标的链域，通过
它可以得到当前的Min, 至于这个下标链，可以放在分离但并排的辅助stack中，也可以
直接作为stack每个item的数据域之一。
如果面试官这样问：
请你设计一个数据结构，使得插入，删除和GetMin都是O(1)时间，你是否能想到并化归
到上面的名题呢？
如果你从来没有见过和准备到这道名题，你可能会好奇的问面试官，这里头对插入和删
除的位置有什么限定。如果面试官告诉你，你就在一端插入和删除吧。这个无意的解释
实际上就是很明显的提示你用stack了。可惜的是，因为不是你自己想到用stack, 面试官可能就会因为这个间接提示去掉一些credits |
x******3
发帖数: 245 | |
b******v
发帖数: 1493 | 3 赞
【在 j**l 的大作中提到】
: 中学数学课时候，老师强调过化归的思想，把陌生的题目情景转化为熟悉的题目情景。
: 面试中也一样。比如下面一道Google名题，后来频频被MSFT, Amazon盗用, 编程之美中
: 也有
: 设计一个stack, 使得Push, Pop和GetMin都是O(1)时间
: 熟悉这题的人都知道，关键是GetMin，为此需要在stack中增加一个下标的链域，通过
: 它可以得到当前的Min, 至于这个下标链，可以放在分离但并排的辅助stack中，也可以
: 直接作为stack每个item的数据域之一。
: 如果面试官这样问：
: 请你设计一个数据结构，使得插入，删除和GetMin都是O(1)时间，你是否能想到并化归
: 到上面的名题呢？
|
r****o
发帖数: 1950 | 4 多谢。
不过请问你怎么用这个下标链在O(1)时间内得到Min呢？
【在 j**l 的大作中提到】
: 中学数学课时候，老师强调过化归的思想，把陌生的题目情景转化为熟悉的题目情景。
: 面试中也一样。比如下面一道Google名题，后来频频被MSFT, Amazon盗用, 编程之美中
: 也有
: 设计一个stack, 使得Push, Pop和GetMin都是O(1)时间
: 熟悉这题的人都知道，关键是GetMin，为此需要在stack中增加一个下标的链域，通过
: 它可以得到当前的Min, 至于这个下标链，可以放在分离但并排的辅助stack中，也可以
: 直接作为stack每个item的数据域之一。
: 如果面试官这样问：
: 请你设计一个数据结构，使得插入，删除和GetMin都是O(1)时间，你是否能想到并化归
: 到上面的名题呢？
|
j**l
发帖数: 2911 | 5 每个链，都指向该元素下方（包含该元素)的最小（不一定是全局最小)，这样栈顶的链，一定指向全局的最小。
【在 r****o 的大作中提到】
: 多谢。
: 不过请问你怎么用这个下标链在O(1)时间内得到Min呢？
|
r****o
发帖数: 1950 | 6 如果栈顶元素最小，结果把它pop了，那下面所有元素的链怎么更新呢？
【在 j**l 的大作中提到】
: 每个链，都指向该元素下方（包含该元素)的最小（不一定是全局最小)，这样栈顶的链，一定指向全局的最小。
|
j**l
发帖数: 2911 | 7 不用更新，请注意我的说法：
每个元素的链，都指向它下方（包含它自身）中的最小元素。
【在 r****o 的大作中提到】
: 如果栈顶元素最小，结果把它pop了，那下面所有元素的链怎么更新呢？
|
r****o
发帖数: 1950 | 8 多谢啊。
【在 j**l 的大作中提到】
: 不用更新，请注意我的说法：
: 每个元素的链，都指向它下方（包含它自身）中的最小元素。
|
y**i
发帖数: 1112 | 9 貌似他假定栈顶是在最上方，下面的元素的链只包含自己下方的元素
【在 r****o 的大作中提到】
: 如果栈顶元素最小，结果把它pop了，那下面所有元素的链怎么更新呢？
|
y**i
发帖数: 1112 | 10 问个基本问题，一般面试的时候，这种自己设计的stack内部用什么数据结构呢，链表
还是用标准库的双端队列或其他什么的？
【在 j**l 的大作中提到】
: 中学数学课时候，老师强调过化归的思想，把陌生的题目情景转化为熟悉的题目情景。
: 面试中也一样。比如下面一道Google名题，后来频频被MSFT, Amazon盗用, 编程之美中
: 也有
: 设计一个stack, 使得Push, Pop和GetMin都是O(1)时间
: 熟悉这题的人都知道，关键是GetMin，为此需要在stack中增加一个下标的链域，通过
: 它可以得到当前的Min, 至于这个下标链，可以放在分离但并排的辅助stack中，也可以
: 直接作为stack每个item的数据域之一。
: 如果面试官这样问：
: 请你设计一个数据结构，使得插入，删除和GetMin都是O(1)时间，你是否能想到并化归
: 到上面的名题呢？
|
|
|
w******1
发帖数: 520 | 11 这么说， 链接指向的数据， 其实是相当于排过序的了
第一个LINK 指向全局最先， 第二个指向第二小。。。。
链，一定指向全局的最小。
【在 j**l 的大作中提到】
: 每个链，都指向该元素下方（包含该元素)的最小（不一定是全局最小)，这样栈顶的链，一定指向全局的最小。
|
b********h
发帖数: 119 | 12 那一次GetMin()之后，是不是所有的链都要更新那？如果这样的话，GetMin就不是O（1
）了。
比如我push 1 - 10, 然后连续调用getmin。每个getmin都要update n个链。复杂度就
是O（n）了。
链，一定指向全局的最小。
【在 j**l 的大作中提到】
: 每个链，都指向该元素下方（包含该元素)的最小（不一定是全局最小)，这样栈顶的链，一定指向全局的最小。
|
j**l
发帖数: 2911 | 13 不需要更新。每当一个元素成为当前的栈顶元素，它的链域指向的一定是全局的最小。
当一个元素还不是栈顶元素的时候，它的链域指向的是它下方的所有元素(括它自己)中
的最小，但全局最小可能在它上方。
（1
【在 b********h 的大作中提到】
: 那一次GetMin()之后，是不是所有的链都要更新那？如果这样的话，GetMin就不是O（1
: ）了。
: 比如我push 1 - 10, 然后连续调用getmin。每个getmin都要update n个链。复杂度就
: 是O（n）了。
:
: 链，一定指向全局的最小。
|
j**l
发帖数: 2911 | 14 你有调用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）了。
:
: 链，一定指向全局的最小。
|
b********h
发帖数: 119 | 15 我懂你的意思。我的意思是说你getmin之后，这个min要不要从堆栈中删除？一旦删除
，所有的链都有可能不准确了。这样必然要更新一次。
当然，如果不需要删除，就不需要更新了。但这样这个getmin连续多次调用的结果都是
一样的。似乎不怎么自然。
【在 j**l 的大作中提到】
: 不需要更新。每当一个元素成为当前的栈顶元素，它的链域指向的一定是全局的最小。
: 当一个元素还不是栈顶元素的时候，它的链域指向的是它下方的所有元素(括它自己)中
: 的最小，但全局最小可能在它上方。
:
: （1
|
b********h
发帖数: 119 | 16 不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
|
j**l
发帖数: 2911 | 17 题目的意思，GetMin就和GetTop一样，是只读操作，不像Push, Pop一样会改变栈。
【在 b********h 的大作中提到】
: 不pop，就getmin。
|
j**l
发帖数: 2911 | 18 如果你不Push新的元素或者Pop已有的元素，连续调用GetMin当然返回同一个值。这道
题主要就是考查如果有更小的元素Push进来，或者当前最小的元素被Pop，如何还能正
确返回min。
【在 b********h 的大作中提到】
: 我懂你的意思。我的意思是说你getmin之后，这个min要不要从堆栈中删除？一旦删除
: ，所有的链都有可能不准确了。这样必然要更新一次。
: 当然，如果不需要删除，就不需要更新了。但这样这个getmin连续多次调用的结果都是
: 一样的。似乎不怎么自然。
|
B*****t
发帖数: 335 | 19 空间利用率不是很好，试想如果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)时间，你是否能想到并化归
: 到上面的名题呢？
|
j**l
发帖数: 2911 | 20 可以这样解决的，栈的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*****t
发帖数: 335 | 21 变量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****o
发帖数: 1950 | 22 你说的当前的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**l
发帖数: 2911 | 23 最坏情况下是这样的。
【在 r****o 的大作中提到】
: 你说的当前的min_id就是末尾的min_id吗？
: 不过这样是不是也有问题，如果跟刚才那个例子相反，每次加入的元素都比前一个小，
: 这样加入10^6个元素的话，vector的size也很客观啊。
:
: GetMin就是取当前的min_id，用它作下标返回栈元素值。
: 就可以了
|
j**l
发帖数: 2911 | 24 我说的那个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****o
发帖数: 1950 | 25 看来没有什么最好的方案啊。
【在 j**l 的大作中提到】
: 最坏情况下是这样的。
|
j**l
发帖数: 2911 | 26 空间换时间，要使得栈在任何时刻都可以有O(1)的GetMin操作，总要付出一定的空间代
价吧。
【在 r****o 的大作中提到】
: 看来没有什么最好的方案啊。
|
