leetcode-155最小栈(历史最值)「建议收藏」

全栈程序员站长

发布于 2022-09-22 09:51:02

3230

文章被收录于专栏：全栈程序员必看全栈程序员必看

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

示例:

输入： [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”] [[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); –> 返回 -3. minStack.pop(); minStack.top(); –> 返回 0. minStack.getMin(); –> 返回 -2.

提示：

pop、top 和 getMin 操作总是在非空栈上调用。题解新开一个栈，存储历史最小值

class MinStack { 
   
public:
    /** initialize your data structure here. */
    stack<int>s;
    stack<int>m;
    MinStack() { 
   
    }
    
    void push(int val) { 
   
        s.push(val);
        if(!m.empty())m.push(min(val,m.top()));
        else m.push(val);
    }
    
    void pop() { 
   
        s.pop();
        m.pop();
    }
    
    int top() { 
   
        return s.top();
    }
    
    int getMin() { 
   
        return m.top();
    }
};

/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168747.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法