一般淘宝网站做几个月赚钱,wordpress建立博客,263企业邮箱入口登录网页版,北京知名的品牌设计公司文章目录1. 题目2. 解题2.1 双栈解法2.2 listmap1. 题目
设计一个最大栈#xff0c;支持 push、pop、top、peekMax 和 popMax 操作。
push(x) -- 将元素 x 压入栈中。
pop() -- 移除栈顶元素并返回这个值。
top() -- 返回栈顶元素。
peekMax() -- 返回栈中最大元素。
popMax…
文章目录1. 题目2. 解题2.1 双栈解法2.2 listmap1. 题目
设计一个最大栈支持 push、pop、top、peekMax 和 popMax 操作。
push(x) -- 将元素 x 压入栈中。
pop() -- 移除栈顶元素并返回这个值。
top() -- 返回栈顶元素。
peekMax() -- 返回栈中最大元素。
popMax() -- 返回栈中最大的元素并将其删除。如果有多个最大元素只要删除最靠近栈顶的那个。样例 1:
MaxStack stack new MaxStack();
stack.push(5);
stack.push(1);
stack.push(5);
stack.top(); - 5
stack.popMax(); - 5
stack.top(); - 1
stack.peekMax(); - 5
stack.pop(); - 1
stack.top(); - 5注释:
-1e7 x 1e7
操作次数不会超过 10000。
当栈为空的时候不会出现后四个操作。来源力扣LeetCode 链接https://leetcode-cn.com/problems/max-stack 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 155. 最小栈
2.1 双栈解法
同时插入数值和最大值当要删除最大的值的时候要将不是最大值的数先存入临时栈后序再挪回来最坏时间复杂度O(n)
class MaxStack {int maxelem INT_MIN;stackint s;stackint temp;int v, m;
public:/** initialize your data structure here. */MaxStack() {}void push(int x) {maxelem max(maxelem, x);s.push(x);s.push(maxelem);}int pop() {s.pop();v s.top();s.pop();maxelem s.empty() ? INT_MIN : s.top();return v;}int top() {m s.top();s.pop();v s.top();s.push(m);return v;}int peekMax() {return s.top();}int popMax() {int ans s.top();maxelem s.top();bool flag true;while(flag){s.pop();if(s.top() ! maxelem)temp.push(s.top());elseflag false;s.pop();}maxelem s.empty() ? INT_MIN : s.top();while(!temp.empty()){v temp.top();temp.pop();s.push(v);maxelem max(maxelem, v);s.push(maxelem);}return ans;}
};140 ms 32.2 MB
2.2 listmap
list 当做栈来使用map的key为数值value挂着数值下对应的list迭代器时间复杂度O(log n)
class MaxStack {listint l;mapint, vectorlistint::iterator m;
public:/** initialize your data structure here. */MaxStack() {}void push(int x) {l.push_front(x);m[x].push_back(l.begin());}int pop() {int v l.front();m[v].pop_back();if(m[v].empty())m.erase(v);l.pop_front();return v;}int top() {return l.front();}int peekMax() {return m.rbegin()-first;}int popMax() {int v m.rbegin()-first;auto it m[v].back();m[v].pop_back();if(m[v].empty())m.erase(v);l.erase(it);return v;}
};240 ms 35.2 MB 长按或扫码关注我的公众号一起加油、一起学习进步
