algorithm - 设计一个数据结构来支持堆栈操作并找到最小值

Question

面试题:设计一个具有以下特点的数据结构

• 推送数据
• 弹出最后插入的数据[LIFO]
• 给出最小值

以上所有操作的复杂度应该是O(1)

Answer 1

你可以通过维护两个堆栈来做到这一点

stack - 在此堆栈上执行通常的 push 和 pop 操作。

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 来稍微优化它，仅当该元素小于当前最小值时。

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