LeetCode 155. 最小栈
2020-05-05 16:00:46来源:博客园 阅读 ()
LeetCode 155. 最小栈
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 155. 最小栈
题目
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop()?—— 删除栈顶的元素。
- top()?—— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
示例:
输入:
["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.
提示:
- pop、top 和 getMin 操作总是在 非空栈 上调用。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
本题核心要解决的是如何记录最小值的问题;
思路1-使用双栈,其中一个为单调递减栈,记录最小值;
步骤:
- 一个栈正常记录数据,一个栈为单调递减栈,只记录比当前栈顶元素小或等于的值(连续相等的值都需要记录,若只记录一次,同值出栈后最小值记录会丢失);
- 出栈时若为当前最小栈的栈顶值则最小栈也出栈;
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
思路2-自己构造节点链表
步骤:
- 定义节点,头节点总记录当前值以及当前最小值;
- 入栈时更新头结点和最小值,出栈时直接更新头结点为其next即可;
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
思路3-使用双数组/list记录
步骤:
- 定义存储数据和最小值的数组,注意最小值的初值处理;
- 入栈出栈等价于改变数组的index,注意数组的扩容问题,此处扩容为原数组的1.5倍;
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
算法源码示例
package leetcode;
import java.util.Arrays;
import java.util.Stack;
/**
* @author ZhouJie
* @date 2020年5月3日 下午4:00:43
* @Description: 155. 最小栈
*
*/
public class LeetCode_0155 {
}
/**
* @author ZhouJie
* @date 2020年5月3日 下午3:23:07
* @Description: 1-两个栈,一个作辅助栈存单调递减值;
*
*/
class MinStack_0155_1 {
private Stack<Integer> data;
private Stack<Integer> min;
/** initialize your data structure here. */
public MinStack_0155_1() {
this.data = new Stack<Integer>();
this.min = new Stack<Integer>();
}
public void push(int x) {
data.push(x);
if (min.isEmpty() || x <= min.peek()) {
min.push(x);
}
}
public void pop() {
if (!data.isEmpty()) {
if (min.peek().intValue() == data.pop().intValue()) {
min.pop();
}
}
}
public int top() {
if (data.isEmpty()) {
return -1;
}
return data.peek();
}
public int getMin() {
if (min.isEmpty()) {
return -1;
}
return min.peek();
}
}
/**
* @author ZhouJie
* @date 2020年5月3日 下午3:23:47
* @Description: 2-构造链表
*
*/
class MinStack_0155_2 {
private Node head;
/** initialize your data structure here. */
public MinStack_0155_2() {
}
public void push(int x) {
if (head == null) {
head = new Node(x, x, null);
} 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 static class Node {
int val;
int min;
Node next;
public Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
/**
* @author ZhouJie
* @date 2020年5月3日 下午3:45:08
* @Description: 3-使用数组保存数据
*
*/
class MinStack_0155_3 {
private int[] data;
private int[] min;
private int head;
private int cap = 1024;
/** initialize your data structure here. */
public MinStack_0155_3() {
this.head = 0;
this.data = new int[cap];
this.min = new int[cap];
min[0] = Integer.MAX_VALUE;
}
public void push(int x) {
if (head == cap - 2) {
// 扩容至原来的1.5倍
cap = cap + (cap >> 1);
data = Arrays.copyOf(data, cap);
min = Arrays.copyOf(min, cap);
}
data[++head] = x;
min[head] = (head == 1) ? x : Math.min(min[head - 1], x);
}
public void pop() {
if (head > 0) {
head--;
}
}
public int top() {
return head > 0 ? data[head] : -1;
}
public int getMin() {
return head > 0 ? min[head] : -1;
}
}
/**
* 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.min();
*/
原文链接:https://www.cnblogs.com/izhoujie/p/12832702.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- LeetCode 287. 寻找重复数 2020-05-31
- 数组小Demo 2020-05-25
- LeetCode 5. 最长回文子串 2020-05-22
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash