[JavaScript] Easy to understand - detailed explanation & O(1) for all
For this problem, we need to implement the push, pop, top, and getMin these 4 methods. Since there is an Array object in JS already, so it\'s straightforward to
For this problem, we need to implement the `push`, `pop`, `top`, and `getMin` these 4 methods. Since there is an `Array` object in JS already, so it\'s straightforward to think about we could be based on it.\n\nThe original `Array` has `push` and `pop` already like a stack. And the `top` method could be easily implemented via `Array.length`. So, the key point for this problem is how to implement the `getMin`.\n\nFor sure, we could sort the array after each `push` operation, but it\'s a general solution and will cost too much. In order to optimize  performance, we need to find out the uniqueness of the current scene and design the strategy based on it.\n\nLet me ask a question, what kinds of positions do we have when we remove values from an array? It\'s straightforward, the middle, the head, and the tail. But, for this problem, it\'s a stack with only `pop` and `push` operations to remove and add values, which means we could only modify the stack at the tail.\n\nWhy this question is so important? Let\'s think, in which situation will the min value change? Bingo - when and only when we modify values. Then, about removing value, since all the previous values are the same, so actually, the min value we have already known won\'t change. In other words, the only situation that we need to compare and get a new min value is when we add a new value.\n\nIf it\'s a little bit abstract, let\'s take a look at an example:\n\nFor array [3, 1, 4, 2, 5, 7], the min value for each index with its previous values is [3, 1, 1, 1, 1].  Whether we remove the last `7` or add new values, then previous min values will always be `[3, 1, 1, 1]`.\n\nAccording to this, we could save all the min values we\'ve known already, this could makes the `getMin` O(1) time complexity.\n\nWe could use another array to save them, but I choose to use just one array - min values and real values are saved one by one. Here\' the code:\n\n```js\nclass MinStack {\n  constructor() {\n    this._top = -1;\n    this.data = [];\n    this.min = Number.MAX_SAFE_INTEGER;\n  }\n  push(n) {\n    this.data[++this._top] = this.min;\n    this.data[++this._top] = n;\n    n < this.min && (this.min = n);\n  }\n  pop() {\n    this.min = this.data[--this._top];\n    --this._top;\n  }\n  top() {\n    return this.data[this._top];\n  }\n  getMin() {\n    return this.min;\n  }\n}\n```
['JavaScript']