中山网站开发招聘,网站建设幽默,密云住房和城乡建设部网站首页,手机网站用什么语言开发#x1f525;博客主页#xff1a; 我要成为C领域大神#x1f3a5;系列专栏#xff1a;【C核心编程】 【计算机网络】 【Linux编程】 【操作系统】 ❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 本博客致力于知识分享#xff0c;与更多的人进行学习交流 设计一个支持 push… 博客主页 我要成为C领域大神系列专栏【C核心编程】 【计算机网络】 【Linux编程】 【操作系统】 ❤️感谢大家点赞收藏⭐评论✍️ 本博客致力于知识分享与更多的人进行学习交流 设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
示例 1:
输入
[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. 辅助栈
思路
创建两个栈一个栈s1正常存放数据另外一个栈s2存放最小值。每次进行push时s1直接调用栈的push操作s2在存放数据时需要进行比较压栈元素与栈顶元素大小关系若新元素大于栈顶元素则重复压入栈顶元素否则压入新元素。最后获取s2的栈顶就是我们要找的最小元素。
代码实现
class MinStack {
public:stackint s1;stackint s2;MinStack() {}void push(int val) {s1.push(val);if (s2.empty())s2.push(val);else if (val s2.top())s2.push(s2.top());elses2.push(val);}void pop() {if (s1.empty())return;if (s2.empty())return;s1.pop();s2.pop();}int top() {if (!s1.empty())return s1.top();elsereturn -1;}int getMin() {if (!s1.empty())return s2.top();elsereturn -1;}
};/*** 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();*/
