当前位置:网站首页>Lecture 1: stack containing min function
Lecture 1: stack containing min function
2022-07-07 09:32:00 【Fight! Sao Nian!】
subject :AcWing 41. contain min Function of the stack
Design a support push,pop,top Wait for operation and can be in O(1) Retrieve the stack of the smallest elements in time .
push(x)– Put the element x Insert into the stack
pop()– Remove the top element
top()– Get the stack top element
getMin()– Get the smallest element in the stack
Data range
Total number of operation commands [0,100].
Examples
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.
Topic analysis :
If this problem does not return the minimum value, then we can directly use the stack , What if you need to return the minimum value ?
We can use auxiliary stack
The sub group stack only stores elements smaller than the top element , Then the top of the auxiliary stack is the minimum value of the current stack .
According to the following figure, we can intuitively feel the relationship between stack and auxiliary stack .
Even if 3 Pop up stack , that 41 Will become the smallest value of the current stack .
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(); */
边栏推荐
- IIS faked death this morning, various troubleshooting, has been solved
- 浏览器中如何让视频倍速播放
- 答案在哪里?action config/Interceptor/class/servlet
- nlohmann json
- Create an int type array with a length of 6. The values of the array elements are required to be between 1-30 and are assigned randomly. At the same time, the values of the required elements are diffe
- Loxodonframework quick start
- [cloud native] Devops (I): introduction to Devops and use of code tool
- Oracle安装增强功能出错
- Octopus future star won a reward of 250000 US dollars | Octopus accelerator 2022 summer entrepreneurship camp came to a successful conclusion
- Postman interface debugging method
猜你喜欢
数据建模中利用3σ剔除异常值进行数据清洗
Detailed learning notes of JVM memory structure (I)
Jenkins task grouping
12、 Sort
Loxodonframework quick start
四、机器学习基础
Install pyqt5 and Matplotlib module
Information Security Experiment 1: implementation of DES encryption algorithm
Mysql database index study notes
超十万字_超详细SSM整合实践_手动实现权限管理
随机推荐
Locust performance test 3 (high concurrency, parameter correlation, assembly point)
nlohmann json
Mysql database transaction learning notes
信息安全实验四:Ip包监视程序实现
Niuke - Huawei question bank (61~70)
Unittest simple project
Using JWT to realize login function
Cesium does not support 4490 problem solution and cesium modified source code packaging scheme
Pytest installation (command line installation)
Pycharm create a new file and add author information
VSCode+mingw64+cmake
ComputeShader
Difference between process and thread
Jenkins modifies the system time
其实特简单,教你轻松实现酷炫的数据可视化大屏
Pick up the premise idea of programming
Create an int type array with a length of 6. The values of the array elements are required to be between 1-30 and are assigned randomly. At the same time, the values of the required elements are diffe
Mysql数据库-锁-学习笔记
Test Engineer Interview Questions 2022
Huawei hcip datacom core_ 03day