`

实现一个Stack,push和pop函数,以及一个输出当前栈内最小值的min函数,要求这三个函数都是O(1)

 
阅读更多
实现一个Stack,push和pop函数,以及一个输出当前栈内最小值的min函数,要求这三个函数都是O(1)


显然,需要时间换空间

栈 A, 辅助栈 minStack,存储最小元素,显然,从栈底到栈顶,非递增

Elem getTop(minStack) {
    return get(minStack);
}

void push(element) {
    if(element <= getTop()) {
        push(element, B);
    }
    push(element, A);
}

void pop() {
    Elem element = pop(A);
    if(element == getTop()) {
        pop(B);
    }
}

Element getMin() {
    return getTop(minStack);
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics