题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); —> 返回 -3.
minStack.pop();
minStack.top(); —> 返回 0.
minStack.min(); —> 返回 -2.

提示：

各函数的调用总次数不超过 20000 次

注意：本题与主站 155 题相同：https://leetcode-cn.com/problems/min-stack/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这个有缺陷，min的复杂度不是 O(1), 而是 O(N)。参考了一下别人的做法，用双栈。
栈A用于普通用处。
栈B用于维护严格大小顺序栈，然后min返回栈顶即可。

  1. /**
  2.  * initialize your data structure here.
  3.  */
  4. var MinStack = function() {
  5.     this.stack = [];
  6. };
  8. /** 
  9.  * @param {number} x
  10.  * @return {void}
  11.  */
  12. MinStack.prototype.push = function(x) {
  13.     this.stack.push(x);
  14. };
  16. /**
  17.  * @return {void}
  18.  */
  19. MinStack.prototype.pop = function() {
  20.     this.stack.pop();
  21. };
  23. /**
  24.  * @return {number}
  25.  */
  26. MinStack.prototype.top = function() {
  27.     return this.stack[this.stack.length - 1];
  28. };
  30. /**
  31.  * @return {number}
  32.  */
  33. MinStack.prototype.min = function() {
  34.     let min = this.stack[0];
  35.     for (let i = 1; i < this.stack.length; i++) {
  36.         if (min > this.stack[i]) min = this.stack[i];
  37.     }
  38.     return min;
  39. };
  41. /**
  42.  * Your MinStack object will be instantiated and called as such:
  43.  * var obj = new MinStack()
  44.  * obj.push(x)
  45.  * obj.pop()
  46.  * var param_3 = obj.top()
  47.  * var param_4 = obj.min()
  48.  */

解2：正确

  1. /**
  2.  * initialize your data structure here.
  3.  */
  4. var MinStack = function() {
  5.     this.stack = [];
  6.     this.minStack = [];
  7. };
  9. /** 
  10.  * @param {number} x
  11.  * @return {void}
  12.  */
  13. MinStack.prototype.push = function(x) {
  14.     this.stack.push(x);
  15.     let minStackLen = this.minStack.length;
  16.     // 这里判定一下。如果这个栈为空或 加入的x小于等于最小栈的栈顶元素，那么就把它加入到最小栈中
  17.     if (minStackLen <= 0 || this.minStack[minStackLen - 1] >= x) {
  18.         this.minStack.push(x);
  19.     }
  20. };
  22. /**
  23.  * @return {void}
  24.  */
  25. MinStack.prototype.pop = function() {
  26.     let x = this.stack.pop();
  27.     // 弹出时判定一下，如果弹出的是最小栈中的元素，那么最小栈也要相应出栈
  28.     if (x == this.minStack[this.minStack.length - 1]) {
  29.         this.minStack.pop();
  30.     }
  31. };
  33. /**
  34.  * @return {number}
  35.  */
  36. MinStack.prototype.top = function() {
  37.     return this.stack[this.stack.length - 1];
  38. };
  40. /**
  41.  * @return {number}
  42.  */
  43. MinStack.prototype.min = function() {
  44.     // 这里就可以直接返回最小栈的栈顶
  45.     return this.minStack[this.minStack.length - 1];
  46. };
  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.min()
  55.  */