【剑指Offer】T30 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的 min 函数(时间复杂度应为 O(1))。

思路:

  • 借助辅助栈实现 stk_mainstk_assist
  • 入栈、出栈、取顶时,主栈都正常操作。
  • 入栈:入主栈,并判断
    • 若辅助栈空:元素入辅助栈
    • 若元素小于辅助栈顶:入辅助栈
  • 出栈:
    • 若两栈顶元素相同(证明栈顶为最小值,否则不会插入),辅助栈出栈。
    • 主栈出栈
  • 取顶:
    • 主栈stk_main.pop()
  • 取最小:直接取辅助栈最小

代码:

stack<int> stk_main, stk_assist;
void push(int value) {
    stk_main.push(value);
    
    if(stk_assist.empty() || value < stk_assist.top())
        stk_assist.push(value);
}
void pop() {
    if(stk_assist.top() == stk_assist.top())
        stk_assist.pop();
    stk_main.pop();
}
int top() {
    return stk_main.top();
}
int min() {
    return stk_assist.top();
}

本文链接:https://ariser.cn/index.php/archives/377/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!