设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈 绝对值?相对值
小结:
1、
常数时间内检索到最小元素
2、存储
存储绝对值?相对值
存储差异
3、
java-ide-debug
最小栈 - 力扣(LeetCode)
https://leetcode-cn.com/problems/min-stack/
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
- push(x) -- 将元素 x 推入栈中。
- pop() -- 删除栈顶的元素。
- top() -- 获取栈顶元素。
- getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
package leetcode; import java.util.Stack; class MinStack {
int min = Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>(); public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();
minStack.pop();
minStack.top();
minStack.getMin();
} public void push(int x) {
// only push the old minimum value when the current
// minimum value changes after pushing the new value x
if (x <= min) {
stack.push(min);
min = x;
}
stack.push(x);
} public void pop() {
// if pop operation could result in the changing of the current minimum value,
// pop twice and change the current minimum value to the last minimum value.
if (stack.pop() == min) min = stack.pop();
} public int top() {
return stack.peek();
} public int getMin() {
return min;
}
}
(3) Clean 6ms Java solution - LeetCode Discuss
https://leetcode.com/problems/min-stack/discuss/49010/Clean-6ms-Java-solution
不借助java stack
package leetcode; class MinStack {
private Node head; public void push(int x) {
if (head == null)
head = new Node(x, x);
else
head = new Node(x, Math.min(x, head.min), head);
} public void pop() {
head = head.next;
} public int top() {
return head.val;
} public int getMin() {
return head.min;
} private class Node {
int val;
int min;
Node next; private Node(int val, int min) {
this(val, min, null);
} private Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
(3) Share my Java solution with ONLY ONE stack - LeetCode Discuss
https://leetcode.com/problems/min-stack/discuss/49031/Share-my-Java-solution-with-ONLY-ONE-stack
The question is ask to construct One stack. So I am using one stack.
The idea is to store the gap between the min value and the current value;
The problem for my solution is the cast. I have no idea to avoid the cast. Since the possible gap between the current value and the min value could be Integer.MAX_VALUE-Integer.MIN_VALUE;
public class MinStack {
long min;
Stack<Long> stack;
public MinStack(){
stack=new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()){
stack.push(0L);
min=x;
}else{
stack.push(x-min);//Could be negative if min value needs to change
if (x<min) min=x;
}
}
public void pop() {
if (stack.isEmpty()) return;
long pop=stack.pop();
if (pop<0) min=min-pop;//If negative, increase the min value
}
public int top() {
long top=stack.peek();
if (top>0){
return (int)(top+min);
}else{
return (int)(min);
}
}
public int getMin() {
return (int)min;
}
}
It's brilliant to store only the difference!! But regarding pop, doesn't it return nothing? Isn't it defined as public void pop(){}
//long pop=stack.pop();
最新文章
- css学习笔记 7
- java切换VPN让你像幽灵一样出现在全国各地
- 在中心交换机前加入多wan口路由,华为中心交换机的学习
- TableView使用CATransform3D特效动画
- C#利用NPOI导出Excel类(简单版)
- RDD的依赖关系
- 有趣的动画视图集合:Android View Animations
- IOS 学习笔记(5) 控件 文本视图(UITextView)的使用方法
- 各浏览器对 window.open() 的窗口特征 sFeatures 参数支持程度存在差异
- Linux 下IOport编程訪问
- Java:利用java Timer类实现定时执行任务的功能
- iWatch # 初始化工程
- Django中使用Bootstrap
- 【Luogu1501】Tree(Link-Cut Tree)
- 电脑开机后win系统运行异常慢,鼠标移动卡
- java保留小数-抄网上的
- python实现文件的复制
- LR常用函数
- CNN 模型压缩与加速算法综述
- LODOP设置判断后执行哪个
热门文章
- ASIHTTPRequest源码简单分析
- iOS7 新后台及下载SDK介绍
- vscode-golang跳转定义无效问题
- Kinect for Windows SDK开发入门(四):景深数据处理 上
- PHP实现月份自动加1
- 《流畅的Python》Data Structures--第7章 colsure and decorator
- 第81题:搜索旋转排序数组II
- 004_linux驱动之_class_create创建一个设备类
- 路由器配置——基于区域的OSPF,MD5认证
- Gradle 如何打包 Spring Boot 如何不添加版本代码