当前位置:网站首页>155. Minimum stack
155. Minimum stack
2022-07-05 12:54:00 【accumulate steadily ض】
Design a support push ,pop ,top operation , And can retrieve the stack of the smallest elements in a constant time .
Realization MinStack class :
- MinStack() Initialize stack object .
- void push(int val) Put the element val Push to stack .
- void pop() Delete the element at the top of the stack .
- int top() Get the element at the top of the stack .
- int getMin() Get the smallest element in the stack .
Input :
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]Output :
[null,null,null,null,-3,null,0,-2]explain :
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> return -3.
minStack.pop();
minStack.top(); --> return 0.
minStack.getMin(); --> return -2.
The question : The meaning of this question is to get the smallest number in the stack , Whether you enter or exit the stack, you finally get the smallest number in the stack .
Ideas : Prepare two stacks , A stack is a normal stack , A stack is a stack that holds the smallest number in the stack , We also call him the minimum stack , When the two stacks are empty at first , We will put elements into these two stacks at the same time , If it's not empty , Put the element into the first ordinary stack , Then compare this element with the smallest stack top element , If it is larger than the minimum stack, the top element of the stack will not be put into the minimum stack , If it is less than the minimum stack, the top element of the stack will be put into the minimum stack .
class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {// Initialize two stacks
stack = new Stack<>();// Ordinary stack
minStack = new Stack<>();// Smallest stack
}
public void push(int val) {
if(stack.empty()&&minStack.empty()){
// Both stacks are empty , meanwhile push Elements
stack.push(val);
minStack.push(val);
}else {
stack.push(val);
if(val<=minStack.peek()){// If it is smaller than the minimum stack top element, enter
minStack.push(val);
}
}
}
public void pop() {// Out of the stack , If the output is the same as the minimum stack top element , Then at the same time, the smallest stack top element , Keep the minimum stack. The top of the stack is still the smallest element in the stack
int x = stack.pop();
if(x==minStack.peek()){
minStack.pop();
}
}
public int top() {// Pop up the common stack top element
return stack.peek();
}
public int getMin() {// The minimum stack top element is the minimum
return minStack.peek();
}
}
边栏推荐
- Compile kernel modules separately
- Didi open source Delta: AI developers can easily train natural language models
- 非技术部门,如何参与 DevOps?
- Wechat enterprise payment to change access, open quickly
- ActiveMQ installation and deployment simple configuration (personal test)
- 10 minute fitness method reading notes (2/5)
- 自然语言处理系列(一)入门概述
- How to connect the API interface of Taobao open platform (super detailed)
- Transactions from December 27 to 28, 2021
- jxl笔记
猜你喜欢
Research: data security tools cannot resist blackmail software in 60% of cases
你的下一台电脑何必是电脑,探索不一样的远程操作
Principle of universal gbase high availability synchronization tool in Nanjing University
【云原生】Nacos-TaskManager 任务管理的使用
研究:数据安全工具在 60% 的情况下无法抵御勒索软件
What is the difference between Bi software in the domestic market
Alipay transfer system background or API interface to avoid pitfalls
Simply take stock reading notes (3/8)
Simply take stock reading notes (2/8)
【Nacos云原生】阅读源码第一步,本地启动Nacos
随机推荐
What if wechat is mistakenly sealed? Explain the underlying logic of wechat seal in detail
奔跑,开路
Kotlin function
Compile kernel modules separately
你的下一台电脑何必是电脑,探索不一样的远程操作
Database connection pool & jdbctemplate
insmod 提示 Invalid module format
Taobao order amount check error, avoid capital loss API
Using MySQL in docker
jxl笔记
Kotlin流程控制、循环
How do e-commerce sellers refund in batches?
关于 SAP UI5 floating footer 显示与否的单步调试以及使用 SAP UI5 的收益
Rasa Chat Robot Tutorial (translation) (1)
Preliminary exploration of basic knowledge of MySQL
Introduction to the principle of DNS
单独编译内核模块
Distributed solution - completely solve website cross domain requests
CVPR 2022 | 基于稀疏 Transformer 的单步三维目标识别器
GPON other manufacturers' configuration process analysis