我在一次采访中被问到：
设计一种数据结构，允许所有这些操作在恒定时间内进行
[1，22，44，56，99，98，56]的范围是98我使用带有两个变量的自定义堆栈来设计它，max和min，但在弹出min或max元素后，这不起作用。
我尝试的内容：
我使用了一个包含两个额外变量max和min的堆栈：
DS
{
top, //Top of the Stack
min, //Min till now
max //Max till now
}
Push(DS, elem)
Push_Stack(DS.top, elem)
if elem < DS.min
DS.min = elem
if elem > DS.max
DS.max = elem
Range(DS)
return DS.max - DS.min
Pop(DS)
x = Pop_Stack(DS.top)
if (x == DS.min)
DS.min = Find_New_Min(DS.top) //This takes linear time using this approach
if (x == DS.max)
DS.max = Find_New_Max(DS.top)
实现一个包含范围函数并在内部使用三个堆栈的“堆栈”。
第一个内部堆栈将表示被推送和弹出的“真实”堆栈。
只有当新元素大于或等于其顶部的元素时，才会将第二个内部堆栈推入。
只有当新元素小于或等于其顶部的元素时，才会推送到第三个内部堆栈。
现在，当你需要计算范围时，只需看一下第二和第三个堆栈的顶部，然后做一些简单的数学运算。
每当需要从“真实”堆栈中弹出一个元素时，请检查该元素是否也在其他两个堆栈的顶部，如果是，也将其从这些堆栈中弹出。
因为你必须以相反的顺序从主堆栈中弹出项目，你永远不会错过其他两个堆栈中的任何东西。。。这意味着第二个和第三个内部堆栈的顶部始终是最大值和最小值。
这类似于Bryon Lo的回答，但在他发布之前，我也发表了同样的评论
维护3个堆栈
Rest是不言而喻的
push(T value)
{
if (value <= min())
{
s2.push(value);
}
if(value >= max())
{
s3.push(value);
}
s1.push(value);
}
T pop()
{
T value = s1.pop();
if (value == min())
{
s2.pop();
}
return value;
}
T min()
{
if (s2.isEmpty())
{
return MAX_VALUE;
}
else {
return s2.peek();
}
}
T max()
{
if (s3.isEmpty())
{
return MIN_VALUE;
}
else
{
return s3.peek();
}
}
