乐趣区

发现数据结构之美栈

jiezi

  • 什么是栈？

    • 数据结构图
    • 入栈出栈图

  • JavaScript 中的 Array 与栈

    • 在 js 中，如何发现出栈 LIFO 的特性？
    • 如何实现一个最小栈？

  • leetcode 栈 解法题目

    • 20. 有效的括号（easy）
    • 67. 二进制求和（easy）
    • 905. 按奇偶排序数组（easy）
    • 56. 合并区间（medium）
    • 75. 颜色分类（medium）
    • 228. 汇总区间（medium）
    • 739. 每日温度（medium）

  • 面试题 栈 解法题目

    • 实现一个 BigInt

什么是栈？

  • 栈是一种后入先出（LIFO）的数据结构
  • 栈通常使用 DFS（Depth First Search）遍历
  • 通常可以通过 top/bottom 来代表栈的顶部和底部

数据结构图

入栈出栈图

JavaScript 中的 Array 与栈

在 js 中，如何发现出栈 LIFO 的特性？

下面这个结构大家都熟悉，瞬间体现出栈 LIFO 的特性。

// 定义一个栈
let stack = [1,2,3];
// 入栈
stack.push(4); // stack [1,2,3,4]
// 出栈
stack.pop(); // 4 stack [1,2,3]

如何实现一个最小栈？

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最小元素。
var MinStack = function() {this.stack = [];
};
MinStack.prototype.push = function(x) {this.stack.push(x);
};
MinStack.prototype.pop = function() {return this.stack.pop();
};
MinStack.prototype.top = function() {return this.stack[this.stack.length - 1];
};
MinStack.prototype.getMin = function() {return Math.min(...this.stack);
};

题目：https://leetcode-cn.com/probl…
解法：https://github.com/FrankKai/l…

leetcode 栈 解法题目

  • 20. 有效的括号（easy）
  • 67. 二进制求和（easy）
  • 905. 按奇偶排序数组（easy）
  • 56. 合并区间（medium）
  • 75. 颜色分类（medium）
  • 228. 汇总区间（medium）
  • 739. 每日温度（medium）

20. 有效的括号（easy）

题目：https://leetcode-cn.com/probl…
题解：https://github.com/FrankKai/l…

/**
   * 解法 2：栈
   * 1. 构建一个栈
   * 2. 依次入栈所有开括号
   * 3. 遇到闭括号时与栈顶的开括号匹配
   *   3.1 若匹配上，出栈并继续
   *   3.2 匹配不上，return false
   * 4. 遍历结束后的栈应该为空，否则为无效括号
   */
var isValid = function(s) {
  var bracketsMap = {"(": ")",
    "{": "}",
    "[": "]"
  };
  var openBrackets = Object.keys(bracketsMap);
  var closeBrackets = Object.values(bracketsMap);
  var stack = [];
  var sArr = s.split("");
  for (var i = 0; i < sArr.length; i++) {if (openBrackets.indexOf(sArr[i]) !== -1) {stack.push(sArr[i]);
    } else if (closeBrackets.indexOf(sArr[i]) !== -1) {var top = stack[stack.length - 1];
      if (sArr[i] === bracketsMap[top]) {stack.pop();
      } else {return false;}
    }
  }
  return stack.length === 0;
}

67. 二进制求和（easy）

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    /**
     * 解法 2：栈
     * 时间复杂度：O(n)
     * 性能：56ms, 35.5MB
     */
    let aArr = a.split("");
    let bArr = b.split("");
    let stack = [];
    let count = 0;
    while (aArr.length !== 0 || bArr.length !== 0) {let aPop = aArr.pop() || 0;
        let bPop = bArr.pop() || 0;
        let stackBottom = 0;
        if (stack.length > count) {stackBottom = stack.shift() || 0;
        }
        let sum = parseInt(aPop) + parseInt(bPop) + parseInt(stackBottom)
        if (sum <= 1) {stack.unshift(sum);
        } else {stack.unshift(sum - 2);
            stack.unshift(1);
        }
        count++;
    }
    return stack.join("");
};

905. 按奇偶排序数组（easy）

题目：https://leetcode-cn.com/probl…
题解：https://github.com/FrankKai/l…

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParity = function (A) {
  /**
   * 栈头栈尾解法即可
   * 偶数栈底推入 unshift
   * 奇数栈顶推入 push
   */
  var stack = [];
  for (var i = 0; i < A.length; i++) {if (A[i] % 2 === 0) {stack.unshift(A[i]);
    } else {stack.push(A[i]);
    }
  }
  return stack;
};

56. 合并区间（medium）

题目：https://leetcode-cn.com/probl…
题解：https://github.com/FrankKai/l…

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  /**
   * 解法 1：排序 + 栈
   * 性能：88ms 36.3MB
   * 思路：* 推入区间 空栈 或者 arr[0] 大于栈最后一个区间闭
   * 覆盖重叠 arr[0] 小于栈最后一个区间闭
   *  */
  intervals.sort((a, b) => a[0] - b[0]);
  let stack = [];
  for (let i = 0; i < intervals.length; i++) {let currrentInterval = intervals[i];
    let stackLastItem = stack[stack.length - 1];
    if (stack.length === 0 || currrentInterval[0] > stackLastItem[1]) {stack.push(currrentInterval);
    } else if (currrentInterval[0] <= stackLastItem[1]) {stackLastItem[1] = Math.max(stackLastItem[1], currrentInterval[1]);
    }
  }
  return stack;
};

75. 颜色分类（medium）

题目：https://leetcode-cn.com/probl…
题解：https://github.com/FrankKai/l…

var sortColors = function (nums) {
  /**
   * 解法 1：递归 栈
   * 性能：64ms 35.1MB
   */
  var length = nums.length;
  var countHead = arguments[1] || 0;
  var countTail = arguments[2] || 0;
  for (var i = countHead || 0; i < length - countTail; i++) {if (nums[i] === 0) {
      countHead++;
      nums.unshift(nums.splice(i, 1)); // 增加 if(i!==0) 会降低 10ms 性能
      return sortColors(nums, countHead, countTail);
    } else if (nums[i] === 2) {
      countTail++;
      nums.push(nums.splice(i, 1));
      return sortColors(nums, countHead, countTail);
    }
  }
  return nums;
}

228. 汇总区间（medium）

题目：https://leetcode-cn.com/probl…
题解：https://github.com/FrankKai/l…

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function (nums) {
  /**
   * 解法 1：排序 + 栈
   * 性能：52ms 33.7MB
   */
  nums.sort((a, b) => a - b);
  let stack = [];
  let result = [];
  for (let i = 0; i < nums.length; i++) {if (stack.length === 0 || nums[i] - stack[stack.length - 1] === 1) {stack.push(nums[i]);
    } else {stackToResult();
      stack = [];
      stack.push(nums[i]);
    }
    if (i === nums.length - 1) {stackToResult();
    }
  }
  function stackToResult() {if (stack.length > 1) {result.push(`${stack[0]}->${stack[stack.length - 1]}`);
    } else {result.push(`${stack[0]}`);
    }
  }
  return result;
};

739. 每日温度（medium）

题目：https://leetcode-cn.com/probl…
题解：https://github.com/FrankKai/l…

  /**
   * 解法 2：栈 + 递归 1132ms 19.96% 59.2MB 11.76%
   * 思路：* 1. 通过 shift 取出栈底元素
   * 2. 遍历剩余温度栈内温度
   *     若温度出现比栈底温度大者
   *         存储 i +1
   *         递归进行下一次入栈
   *     若温度小于等于栈底温度
   *         若遍历到最后一个都没有出现更大的
   *              存储 0
   *              进行下一次入栈
   * 3. 最后一个温度无论如何都肯定是 0
   */
var dailyTemperatures = function(T) {if (T.length < 1 || T.length > 30000) return false;
  var result = arguments[1] || [];
  var bottom = T.shift();
  for (var i = 0; i < T.length; i++) {var t = T[i];
    if (t > bottom) {result.push(i + 1);
      return dailyTemperatures(T, result);
    } else {if (i === T.length - 1) {result.push(0);
        return dailyTemperatures(T, result);
      }
    }
  }
  result.push(0);
  return result;
}

面试题 栈 解法题目

实现一个 BigInt

实现大整数相加，大于 Number.MAX_VALUE，不能直接使用 BigInt。

/**
* 请通过代码实现大整数（可能比 Number.MAX_VALUE 大）相加运算
// your code goes here
var bigint1 = new BigInt('1231230');
var bigint2 = new BigInt('12323123999999999999999999999999999999999999999999999991');
console.log(bigint1.plus(bigint2))
*/
function BigInt(value) {this.value = value;}

BigInt.prototype.plus = function (bigint) {let aArr = this.value.split("");
  let bArr = bigint.value.split("");
  let stack = [];
  let count = 0;
  while (aArr.length !== 0 || bArr.length !== 0) {let aPop = aArr.pop() || 0;
    let bPop = bArr.pop() || 0;
    let stackBottom = 0;
    if (stack.length > count) {stackBottom = stack.shift();
    }
    let sum = parseInt(aPop) + parseInt(bPop) + parseInt(stackBottom);
    if (sum < 10) {stack.unshift(sum);
    } else if (sum >= 10) {stack.unshift(sum - 10);
      stack.unshift(1);
    }
    count++;
  }
  return stack.join("");
};

期待和大家交流，共同进步，欢迎大家加入我创建的与前端开发密切相关的技术讨论小组：

  • 微信公众号：生活在浏览器里的我们 / excellent_developers
  • Github 博客: 趁你还年轻 233 的个人博客
  • SegmentFault 专栏：趁你还年轻，做个优秀的前端工程师
  • Leetcode 讨论微信群：Z2Fva2FpMjAxMDA4MDE=（加我微信拉你进群）

努力成为优秀前端工程师！

退出移动版