Skip to content

0155-min-stack.adoc

Latest commit

 

History

History
106 lines (79 loc) · 2.73 KB

0155-min-stack.adoc

File metadata and controls

106 lines (79 loc) · 2.73 KB

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。

  • void push(int val) 将元素val推入堆栈。

  • void pop() 删除堆栈顶部的元素。

  • int top() 获取堆栈顶部的元素。

  • int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["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.

提示：

  • -231 <= val <= 231 - 1

  • pop、top 和 getMin 操作总是在 非空栈 上调用

  • push, pop, top, and getMin`最多被调用 `3 * 104 次

思路分析

使用两个栈，一个栈存原始数据，另外一个栈存当前栈的最小值。

{image_attr}

不比每次都向最小栈里面添加数据，只在出现更小值的时候才向最小栈中添加数据。如下图：

{image_attr}
一刷
link:{sourcedir}/_0155_MinStack.java[role=include]
二刷
link:{sourcedir}/_0155_MinStack_2.java[role=include]
三刷
link:{sourcedir}/_0155_MinStack_3.java[role=include]
四刷
link:{sourcedir}/_0155_MinStack_4.java[role=include]