设计数据结构以支持堆栈操作并找到最小值

Question

面试问题:设计具有以下功能的数据结构

• 推送数据
• 弹出最后插入的数据[LIFO]
• 给予最低限度

所有上述操作都应该具有复杂性 O(1)

Answer 1

您可以通过维护两个堆栈来完成此操作

stack - 在此堆栈上执行常规的推送和弹出操作.

minStack- 此堆栈用于及时获取堆栈中的最小元素O(1).在任何时候,该堆栈的顶部元素将是堆栈中所有元素的最小值.

push( item a) 
    // push the element on the stack.
    stack.push(a)   

    // find the min of the ele to be pushed and the ele on top of minStack.
    if(minStack.isEmpty()) 
        min = a
    else
        min = Min(a,minStack.top())

    // push the min ele on the minStack.
    minStack.push(min) 
end push


pop()
    // pop and discard
    minStack.pop() 

    // pop and return
    return stack.pop() 
end pop


findMin()
    return minStack.top()
end findMin

在上述解决方案中,每次将元素推入堆栈时,都会进行相应的推送minStack.所以在任何时候堆栈中的元素数量minStack都是相同的.我们可以通过minStack仅在元素小于当前min时将元素推到上面来稍微优化它.

push( item a) 
    // push the element on the orginal stack.
    stack.push(a)   

    if(minStack.isEmpty())
            // if minStack is empty push.
            minStack.push(a) 
    // else push only if the element is less than or equal to the present min.
    else if(a <= minStack.top()) 
        minStack.push(a)
end push

pop()
    // pop from the stack
    ele = stack.top()     
    if(minStack.top() == ele)
            // pop only if the top element is ele.
        minStack.pop() 

    // return the popped element.
    return ele 
end pop