常见面试算法题JS实现-设计一个有getMin功能的栈

2018-07-18 01:42:45来源：博客园阅读 ()

前言：

　　已经确定工作了～下周一正式入职，按理说应该是可以好好浪荡一周的，但是内心总是不安，总觉得自己这个水平真的太菜了，还是趁着现在有自己的时间，赶紧多看看书，多学习学习吧orz所以把之前校招买的书，又翻出来看，都是很经典的书，但是因为自己找到工作之后就放纵了，几乎都放在书架上长灰，现在拿出来，一是希望自己能够养成一个学习的好习惯，即使在工作忙的时候，依然要挤出一点时间学习新的知识，不能得过且过，二是希望记录一下正在努力时的自己，也算是跟想要偷懒时的自己说，“喂，懒鬼，快点学习，不然你就真的对不起曾经努力的自己和以后懊悔的自己了”，嗯呢，闲话又说多了，接下来就正式开始咯～

正文：

　　【题目】实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

　　【要求】1. pop、push、getMin操作的时间复杂度都为O(1)

　　　　　　2. 设计的栈类型可以使用现成的栈结构

　　【思路】定义一个stackData和一个stackMin，stackData用于存放实际数据，stackMin用于存放stackData中的最小值。重写pop和push方法，实现stackData和stackMin的数据同步。

　　【实现】实现的方式有两种，详见代码。

 // 方法一
 1 class MyStack {
 2     constructor() {
 3         this.stackData = [];
 4         this.stackMin = [];
 5     }
 6     push() {
 7         let args = arguments[0];
 8         if (typeof args === 'number') {
 9             //将新数据压入stackData栈中
10             this.stackData.push(args);
11             //判断是否将新数据压入stackMin栈中
12             if (this.stackMin.length > 0) {
13                 //stackMin栈不空，需要判断当前数据是否小于等于stackMin的栈顶元素
14                 let top = this.getMin();
15                 if (args <= top) {
16                     this.stackMin.push(args);
17                 }
18             } else {
19                 //stackMin栈空，则压入
20                 this.stackMin.push(args);
21             }
22         }
23     }
24     pop() {
25         if (this.stackMin.length === 0) {
26             throw new Error('Stack is empty!');
27         }
28         let p = this.stackData.pop();
29         let top = this.getMin();
30         if (p === top) {
31             this.stackMin.pop();
32         }
33         return p;
34     }
35     getMin() {
36         if (this.stackMin.length === 0) {
37             throw new Error('Stack is empty!');
38         }
39         let len = this.stackMin.length;
40         return this.stackMin[len - 1];
41     }
42 }
43 
44 let s = new MyStack();
45 s.push(4);
46 s.push(2);
47 s.push(1);
48 console.log(s.getMin());
49 s.pop();
50 console.log(s.getMin());
51 s.pop();
52 s.pop();
53 s.pop();    //抛出异常

 //方法二
 1 class MyStack {
 2     constructor() {
 3         this.stackData = [];
 4         this.stackMin = [];
 5     }
 6     push() {
 7         let args = arguments[0];
 8         if (typeof args === 'number') {
 9             //将新数据压入stackData栈中
10             this.stackData.push(args);
11             //判断是否将新数据压入stackMin栈中
12             if (this.stackMin.length > 0) {
13                 //stackMin栈不空，需要判断当前数据是否小于等于stackMin的栈顶元素
14                 let top = this.getMin();
15                 if (args <= top) {
16                     this.stackMin.push(args);
17                 } else {
18                     this.stackMin.push(top);
19                 }
20             } else {
21                 //stackMin栈空，则压入
22                 this.stackMin.push(args);
23             }
24         }
25     }
26     pop() {
27         if (this.stackMin.length === 0) {
28             throw new Error('Stack is empty!');
29         }
30         let p = this.stackData.pop();
31         this.stackMin.pop();
32         return p;
33     }
34     getMin() {
35         if (this.stackMin.length === 0) {
36             throw new Error('Stack is empty!');
37         }
38         let len = this.stackMin.length;
39         return this.stackMin[len - 1];
40     }
41 }
42 
43 let s = new MyStack();
44 s.push(4);
45 s.push(2);
46 s.push(1);
47 console.log(s.getMin());
48 s.pop();
49 console.log(s.getMin());
50 s.pop();
51 s.pop();
52 // s.pop();    //抛出异常

后话：

　　这个是计划写成一个系列，主要参考的就是左大神的《程序员代码面试指南——IT名企算法与数据结构题目最优解》，左大神在书里是用JAVA实现的，基本看得懂，但是因为我是用JS的，总觉得差点意思，反正也是学习，干脆就自己实现JS的写法，并且分享出来，也算是让我继续坚持的一个动力，当然，因为本人是菜鸟小白，肯定或多或少会出现一些问题，希望各位大牛们在嘲笑之余能够请不吝赐教～康桑阿米达～阿尼嘎多～Thx～谢谢～

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有