当前位置:网站首页>第一讲:包含min函数的栈
第一讲:包含min函数的栈
2022-07-07 06:51:00 【奋斗吧!骚年!】
题目:AcWing 41. 包含min函数的栈
设计一个支持push,pop,top等操作并且可以在O(1)时间内检索出最小元素的堆栈。
push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素
数据范围
操作命令总数 [0,100]。
样例
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin(); --> Returns -4.
minStack.pop();
minStack.top(); --> Returns 3.
minStack.getMin(); --> Returns -1.
题目分析:
这道题如果没有返回最小值那么我们可以直接使用栈,那么如果需要返回最小值呢?
我们可以使用辅助栈
辅组栈只保存比栈顶元素小的元素,那么辅助栈的栈顶就是当前栈的最小值。
根据观看下图我们可以很直观感受到栈和辅助栈的关系。
即使 3 弹出栈,那么 41 将成为当前栈最小的值。
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
stk.push(x);
if(min_stk.empty()||min_stk.top()>=x)min_stk.push(x);
}
void pop() {
if(min_stk.top()==stk.top())min_stk.pop();
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return min_stk.top();
}
private:
stack<int> stk,min_stk;
};
/** * 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.getMin(); */
边栏推荐
- How long does the PMP usually need to prepare for the exam in advance?
- Information Security Experiment 1: implementation of DES encryption algorithm
- Skill review of test engineer before interview
- Storage of data in memory
- Information Security Experiment 2: using x-scanner scanning tool
- Schema-validation: wrong column type encountered in column XXX in table XXX
- 四、机器学习基础
- The configuration and options of save actions are explained in detail, and you won't be confused after reading it
- stm32和电机开发(从单机版到网络化)
- Register address name mapping
猜你喜欢
Skill review of test engineer before interview
JWT certification used in DRF
Locust performance test 2 (interface request)
C language pointer (special article)
華為HCIP-DATACOM-Core_03day
Kubernetes cluster capacity expansion to add node nodes
What is the use of PMP certificate?
Loxodonframework quick start
四、机器学习基础
Mysql database index study notes
随机推荐
信息安全实验二 :使用X-SCANNER扫描工具
How can I apply for a PMP certificate?
Windows starts redis service
Schema-validation: wrong column type encountered in column XXX in table XXX
Locust performance test 5 (analysis)
Loxodonframework quick start
PMP certificate preparation experience sharing
Entity of cesium data visualization (Part 1)
Kubernetes cluster capacity expansion to add node nodes
Netease cloud wechat applet
PMP Exam details after the release of the new exam outline
Cesium load vector data
二叉树高频题型
What is the use of PMP certificate?
ComputeShader
Leetcode question brushing record (array) combination sum, combination sum II
Detailed learning notes of JVM memory structure (I)
Locust performance test 3 (high concurrency, parameter correlation, assembly point)
【云原生】DevOps(一):DevOps介绍及Code工具使用
NVIC interrupt priority management