155. Min Stack javascript解題

更新於 分類於 閱讀次數：

題目說明

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 element val 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.

Input / Output(測試資料輸入/輸出):

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 and getMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.

解題思路

在Leetcode算Easy的題目，複習Stack堆疊先進後出的觀念，以下以實作上較特別的功能函數做說明

push()

每次推之前都檢查推的值是否比 min 存的值還小，有就存進去

所以 min 最底層永遠是最小值

pop()

每次移除最後一個值之前都檢查移除的值是否與 min 存的值相等，有就順便移除掉

最後一個值 => 最早 push 進堆疊的數值 => 維持 min 裡面最後一項永遠最小

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var MinStack = function() {  
    this.stack = [];
    this.min = [];
};

MinStack.prototype.push = function(val) {
    if(this.min.length === 0 || val <= this.getMin()){
        this.min.push(val);
    }
    this.stack.push(val);
}; 

MinStack.prototype.pop = function() {
     if(this.getMin()  === this.top()){
        this.min.pop();
    }
    this.stack.pop();
};

MinStack.prototype.top = function() {
    return  this.stack[ this.stack.length-1];
};

MinStack.prototype.getMin = function() {
     return  this.min[ this.min.length-1];
};