题目

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

思路分析

使用两个栈来存储数据，其中一个命名为 data_stack，专门用来存储数据，另一个命名为 min_stack，专门用来存储栈里最小的元素。

  1. 我们实现一个栈，除了有常规的方法，还要有一个 min 方法。data_stack 就是专门为常规方法而存在的，min_stack 就是为了这个 min 方法而存在的。
  2. 编程思想里有一个分而治之的思想，简单来说，就是分开想，分开处理。那么我们现在考虑 data_stack，这个时候别管 min 方法，只关心data_stack，它就是一个普通的栈，没什么特别的，就实现栈的常规方法 push、pop等就可以了。
  3. data_stack 处理完了以后，再考虑 min_stack。这个时候，别再想 data_stack 了，只关心 min_stack，它要存储栈里的最小值。我们先考虑边界情况，如果 min_stack 为空，这个时候，如果 push 进来一个数据，那这个数据一定是最小的，所以此时，直接放入 min_stack 即可。如果 min_stack 不为空，这个时候它的栈顶是最小的元素(min_stack的栈顶永远是最小的元素)，如果push进来的元素比栈顶元素还小，放入min_stack就好了，这样，就能保证min_stack的栈顶始终都是栈里的最小值。


代码实现

Stack

  1. class Stack {
  2.   constructor() {
  3.     this.count = 0;
  4.     this.items = {};
  5.   }
  6.   push(element) {
  7.     this.items[this.count] = element;
  8.     this.count++;
  9.   }
  10.   pop() {
  11.     if (this.isEmpty()) {
  12.       return undefined;
  13.     }
  14.     this.count--;
  15.     const result = this.items[this.count];
  16.     delete this.items[this.count];
  17.     return result;
  18.   }
  19.   top() {
  20.     if (this.isEmpty()) {
  21.       return undefined;
  22.     }
  23.     return this.items[this.count - 1];
  24.   }
  25.   isEmpty() {
  26.     return this.count === 0;
  27.   }
  28.   size() {
  29.     return this.count;
  30.   }
  31.   clear() {
  32.     /* while (!this.isEmpty()) {
  33.         this.pop();
  34.       } */
  35.     this.items = {};
  36.     this.count = 0;
  37.   }
  38.   toString() {
  39.     if (this.isEmpty()) {
  40.       return '';
  41.     }
  42.     let objString = `${this.items[0]}`;
  43.     for (let i = 1; i < this.count; i++) {
  44.       objString = `${objString},${this.items[i]}`;
  45.     }
  46.     return objString;
  47.   }
  48. }

MinStack

  1. class MinStack {
  2.     constructor() {
  3.       this.data_stack = new Stack();
  4.     this.min_stack = new Stack();
  5.   }
  7.   // pop 的时候，两个栈都pop，保持两个栈中的元素个数都一致
  8.   pop() {
  9.       this.min_stack.pop();
  10.     return this.data_stack.pop();
  11.   }
  13.   // 直接取 min_stack 栈顶的元素
  14.   min() {
  15.       return this.min_stack.top()
  16.   }
  18.   push(ele) {
  19.     // data_stack 栈按正常方式将元素入栈
  20.       this.data_stack.push(ele);
  22.     // 如果 min_stack 为空，则直接将元素入栈
  23.     // 如果 ele 小于 min_stack 的栈顶元素，则将元素入栈
  24.     // 这样做的目的，是保证 min_stack 的栈顶始终保存栈的最小值
  25.     if (this.min_stack.isEmpty() || ele < this.min_stack.top()) {
  26.         this.min_stack.push(ele)
  27.     } else {
  28.       // 如果 ele 大于等于 min_stack 的栈顶元素，则将min_stack 的栈顶元素再放入一次
  29.       // min_stack 和 data_stack 的元素个数要保持一致
  30.         this.min_stack.push(this.min_stack.top())
  31.     }
  32.   }
  33. }
  37. const minStack = new MinStack();
  39. minStack.push(3);
  40. minStack.push(6);
  41. minStack.push(8);
  43. console.log(minStack)
  44. console.log(minStack.min()); // 3
  45. minStack.push(2);
  46. console.log(minStack)
  47. console.log(minStack.min()); // 2