[LeetCode] 155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack
class:
MinStack()
initializes the stack object.void push(int val)
pushes the elementval
onto the stack.void pop()
removes the element on the top of the stack.int top()
gets the top element of the stack.int getMin()
retrieves the minimum element in the stack.
Example 1:
Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation 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
Constraints:
-231 <= val <= 231 - 1
- Methods
pop
,top
andgetMin
operations will always be called on non-empty stacks. - At most
3 * 104
calls will be made topush
,pop
,top
, andgetMin
.
最小栈。
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这个题我给出两种解法,一种用了两个 stack,一种只需要用一个 stack。两种做法的复杂度都是
时间O(1)
空间O(n)
1. 两个 stack。创建两个 stack,一个叫 stack,另一个叫做 minstack。
push() - 每当需要 push 的时候,每个元素都会被正常 push 到 stack,同时需要看一下当前元素与全局最小元素 min 的关系,以决定是否需要把这个元素 push 到 minStack。minStack 只 push 当前遍历到的最小值。
pop() - stack 会正常 pop 出当前元素;因为 minStack 的顶端存的永远是当前的最小值,所以当 stack 弹出一个元素 X 的时候,需要去 minStack 的栈顶看一下 X 是不是最小值,也就是看一下 minStack 的栈顶是不是也是 X,如是,也需要从 minStack 弹出,这样 minStack 顶端保留的永远是最小值。
top() - 同 peek(),只是看一下 stack 顶端的元素
getMin() - 去 peek minStack 顶端的元素,因为 minStack 的顶端永远是当前遍历到的最小值
JavaScript实现
1 /** 2 * initialize your data structure here. 3 */ 4 var MinStack = function () { 5 this.stack = []; 6 this.minStack = []; 7 }; 8 9 /** 10 * @param {number} x 11 * @return {void} 12 */ 13 MinStack.prototype.push = function (x) { 14 this.stack.push(x); 15 if (this.minStack.length) { 16 let top = this.minStack[this.minStack.length - 1]; 17 if (x <= top) { 18 this.minStack.push(x); 19 } 20 } else { 21 this.minStack.push(x); 22 } 23 }; 24 25 /** 26 * @return {void} 27 */ 28 MinStack.prototype.pop = function () { 29 let pop = this.stack.pop(); 30 let top = this.minStack[this.minStack.length - 1]; 31 if (pop === top) { 32 this.minStack.pop(); 33 } 34 }; 35 36 /** 37 * @return {number} 38 */ 39 MinStack.prototype.top = function () { 40 return this.stack[this.stack.length - 1]; 41 }; 42 43 /** 44 * @return {number} 45 */ 46 MinStack.prototype.getMin = function () { 47 return this.minStack[this.minStack.length - 1]; 48 }; 49 50 /** 51 * Your MinStack object will be instantiated and called as such: 52 * var obj = new MinStack() 53 * obj.push(x) 54 * obj.pop() 55 * var param_3 = obj.top() 56 * var param_4 = obj.getMin() 57 */
Java实现
1 class MinStack { 2 private Stackstack; 3 private Stack minStack; 4 /** initialize your data structure here. */ 5 public MinStack() { 6 stack = new Stack<>(); 7 minStack = new Stack<>(); 8 } 9 10 public void push(int x) { 11 stack.push(x); 12 if (!minStack.isEmpty()) { 13 int min = minStack.peek(); 14 if (x <= min) { 15 minStack.push(x); 16 } 17 } else { 18 minStack.push(x); 19 } 20 } 21 22 public void pop() { 23 int x = stack.pop(); 24 if (x == minStack.peek()) { 25 minStack.pop(); 26 } 27 } 28 29 public int top() { 30 return stack.peek(); 31 } 32 33 public int getMin() { 34 return minStack.peek(); 35 } 36 } 37 38 /** 39 * Your MinStack object will be instantiated and called as such: 40 * MinStack obj = new MinStack(); 41 * obj.push(x); 42 * obj.pop(); 43 * int param_3 = obj.top(); 44 * int param_4 = obj.getMin(); 45 */
2. 一个 stack,同时创建一个变量记录最小值 min。
push() - push 的时候看一下当前元素是否比 min 小,若是则把上一个min放进stack,同时更新当前最小值 min。
pop() - 如果弹出值 == 当前最小值,那么再弹一次的值为上一个最小值也即出栈后更新的最小值
top() - 同 peek,只是看一下 stack 顶端的元素
getMin() - 输出 min 即可
JavaScript实现
1 /** 2 * initialize your data structure here. 3 */ 4 var MinStack = function () { 5 this.stack = []; 6 this.min = Number.MAX_SAFE_INTEGER; 7 }; 8 9 /** 10 * @param {number} x 11 * @return {void} 12 */ 13 MinStack.prototype.push = function (x) { 14 // 当前值比min值更小 15 if (this.min >= x) { 16 // 将上一个min最小值保存入栈 17 this.stack.push(this.min); 18 // 更新当前最小值 19 this.min = x; 20 } 21 this.stack.push(x) 22 }; 23 24 /** 25 * @return {void} 26 */ 27 MinStack.prototype.pop = function () { 28 // 如果弹出值 == 当前最小值,那么再弹一次的值为上一个最小值也即出栈后更新的最小值 29 if (this.stack.pop() == this.min) { 30 this.min = this.stack.pop(); 31 } 32 }; 33 34 /** 35 * @return {number} 36 */ 37 MinStack.prototype.top = function () { 38 return this.stack[this.stack.length - 1]; 39 }; 40 41 /** 42 * @return {number} 43 */ 44 MinStack.prototype.getMin = function () { 45 return this.min; 46 }; 47 48 /** 49 * Your MinStack object will be instantiated and called as such: 50 * var obj = new MinStack() 51 * obj.push(x) 52 * obj.pop() 53 * var param_3 = obj.top() 54 * var param_4 = obj.getMin() 55 */
Java实现
1 class MinStack { 2 int min = Integer.MAX_VALUE; 3 Stackstack = new Stack<>(); 4 5 /** initialize your data structure here. */ 6 public MinStack() { 7 8 } 9 10 public void push(int x) { 11 if (x <= min) { 12 stack.push(min); 13 min = x; 14 } 15 stack.push(x); 16 } 17 18 public void pop() { 19 if (stack.pop() == min) { 20 min = stack.pop(); 21 } 22 } 23 24 public int top() { 25 return stack.peek(); 26 } 27 28 public int getMin() { 29 return min; 30 } 31 } 32 33 /** 34 * Your MinStack object will be instantiated and called as such: 35 * MinStack obj = new MinStack(); 36 * obj.push(x); 37 * obj.pop(); 38 * int param_3 = obj.top(); 39 * int param_4 = obj.getMin(); 40 */
相关题目