前言:
已经确定工作了~下周一正式入职, 按理说应该是可以好好浪荡一周的, 但是内心总是不安, 总觉得自己这个水平真的太菜了, 还是趁着现在有自己的时间, 赶紧多看看书, 多学习学习吧 orz 所以把之前校招买的书, 又翻出来看, 都是很经典的书, 但是因为自己找到工作之后就放纵了, 几乎都放在书架上长灰, 现在拿出来, 一是希望自己能够养成一个学习的好习惯, 即使在工作忙的时候, 依然要挤出一点时间学习新的知识, 不能得过且过, 二是希望记录一下正在努力时的自己, 也算是跟想要偷懒时的自己说,"喂, 懒鬼, 快点学习, 不然你就真的对不起曾经努力的自己和以后懊悔的自己了", 嗯呢, 闲话又说多了, 接下来就正式开始咯~
正文:
[题目] 实现一个特殊的栈, 在实现栈的基本功能的基础上, 再实现返回栈中最小元素的操作.
[要求] 1. pop,push,getMin 操作的时间复杂度都为 O(1)
2. 设计的栈类型可以使用现成的栈结构
[思路] 定义一个 stackData 和一个 stackMin,stackData 用于存放实际数据, stackMin 用于存放 stackData 中的最小值. 重写 pop 和 push 方法, 实现 stackData 和 stackMin 的数据同步.
[实现] 实现的方式有两种, 详见代码.
- // 方法一
- class MyStack {
- constructor() {
- this.stackData = [];
- this.stackMin = [];
- }
- push() {
- let args = arguments[0];
- if (typeof args === 'number') {
- // 将新数据压入 stackData 栈中
- this.stackData.push(args);
- // 判断是否将新数据压入 stackMin 栈中
- if (this.stackMin.length > 0) {
- //stackMin 栈不空, 需要判断当前数据是否小于等于 stackMin 的栈顶元素
- let top = this.getMin();
- if (args <= top) {
- this.stackMin.push(args);
- }
- } else {
- //stackMin 栈空, 则压入
- this.stackMin.push(args);
- }
- }
- }
- pop() {
- if (this.stackMin.length === 0) {
- throw new Error('Stack is empty!');
- }
- let p = this.stackData.pop();
- let top = this.getMin();
- if (p === top) {
- this.stackMin.pop();
- }
- return p;
- }
- getMin() {
- if (this.stackMin.length === 0) {
- throw new Error('Stack is empty!');
- }
- let len = this.stackMin.length;
- return this.stackMin[len - 1];
- }
- }
- let s = new MyStack();
- s.push(4);
- s.push(2);
- s.push(1);
- console.log(s.getMin());
- s.pop();
- console.log(s.getMin());
- s.pop();
- s.pop();
- s.pop(); // 抛出异常
- // 方法二
- class MyStack {
- constructor() {
- this.stackData = [];
- this.stackMin = [];
- }
- push() {
- let args = arguments[0];
- if (typeof args === 'number') {
- // 将新数据压入 stackData 栈中
- this.stackData.push(args);
- // 判断是否将新数据压入 stackMin 栈中
- if (this.stackMin.length > 0) {
- //stackMin 栈不空, 需要判断当前数据是否小于等于 stackMin 的栈顶元素
- let top = this.getMin();
- if (args <= top) {
- this.stackMin.push(args);
- } else {
- this.stackMin.push(top);
- }
- } else {
- //stackMin 栈空, 则压入
- this.stackMin.push(args);
- }
- }
- }
- pop() {
- if (this.stackMin.length === 0) {
- throw new Error('Stack is empty!');
- }
- let p = this.stackData.pop();
- this.stackMin.pop();
- return p;
- }
- getMin() {
- if (this.stackMin.length === 0) {
- throw new Error('Stack is empty!');
- }
- let len = this.stackMin.length;
- return this.stackMin[len - 1];
- }
- }
- let s = new MyStack();
- s.push(4);
- s.push(2);
- s.push(1);
- console.log(s.getMin());
- s.pop();
- console.log(s.getMin());
- s.pop();
- s.pop();
- // s.pop(); // 抛出异常
后话:
这个是计划写成一个系列, 主要参考的就是左大神的程序员代码面试指南 --IT 名企算法与数据结构题目最优解, 左大神在书里是用 JAVA 实现的, 基本看得懂, 但是因为我是用 JS 的, 总觉得差点意思, 反正也是学习, 干脆就自己实现 JS 的写法, 并且分享出来, 也算是让我继续坚持的一个动力, 当然, 因为本人是菜鸟小白, 肯定或多或少会出现一些问题, 希望各位大牛们在嘲笑之余能够请不吝赐教~康桑阿米达~阿尼嘎多~Thx~谢谢~
来源: https://www.cnblogs.com/zllwebstudy/p/9324287.html