我在一次采访中被问到这个问题:
设计一个数据结构,允许所有这些操作在常数 , O(1)
, 时间:
- 推送一个元素
- 弹出一个元素
- 元素范围:查找当前元素的最小区间范围。
例如。的范围[1, 22, 44, 56, 99, 98, 56]
是98
。
我使用带有两个变量max
和的自定义堆栈来设计它min
,但是在弹出最小或最大元素后这不起作用。
我尝试了什么:
我使用了一个带有两个额外变量 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)