【题解】剑指Offer-30 包含min函数的栈 发表于 2021-04-03 分类于 题解 , 基础 , 水题 本文字数: 186 阅读时长 ≈ 1 分钟剑指Offer-30 包含min函数的栈 类型 水题包含min函数的栈(剑指Offer-30)题面定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。示例12345678MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.min(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.min(); --> 返回 -2.限制1各函数的调用总次数不超过 20000 次思路除了常规的栈,再维护一个单调栈,从栈顶到栈底递增常规栈常规添加删除元素单调栈栈顶元素大于等于待加入元素或者单调栈为空,则入栈;当常规栈的出栈元素等于单调栈的栈顶元素,单调栈出栈代码12345678910111213141516171819202122232425262728293031323334353637class MinStack { stack<int> s, t;public: /** initialize your data structure here. */ MinStack() { } void push(int x) { if(t.empty() || t.top() >= x) t.push(x); s.push(x); } void pop() { if(t.top() == s.top()) t.pop(); s.pop(); } int top() { return s.top(); } int min() { return t.top(); }};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->min(); */