Разработайте datastructure, чтобы поддерживать операции стека и найти минимум

Вы можете сделать это, поддерживая два стека

стек - выполняйте обычные операции 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 , только если элемент меньше текущего 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