hailiting Blog

# 堆和栈

# 栈 典型的后进先出

const stack = [];
stack.push(1);
stack.push(2);
const item1 = stack.pop();
const items = stack.pop();

# 栈的应用场景

    1. 十进制转二进制
    1. 判断字符串的括号是否有效 ()()() （（（（（（（））））））） 入栈 出栈 栈空的是合法的
    1. 函数调用堆栈 最后调用的函数 最早被执行完 调用堆栈

# leetCode

20: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  // 新建一个新的栈
  // 扫描字符串，遇到左括号入栈，遇到和栈顶括号类型匹配的右括号就出栈，类型不匹配直接判定为不合法
  // 最后栈空则合法，否则不合法
  if (s.length % 2 !== 0) {
    return false;
  }
  let stack = [];
  const len = s.length;
  for (let i = 0; i < len; i++) {
    // 时间复杂度 O(n)  空间复杂度 O(n)
    const c = s[i];
    if (c === "{" || c === "[" || c === "(") {
      stack.push(c);
    } else {
      const t = stack[stack.length - 1]; // 后进
      if (
        (c === ")" && t === "(") ||
        (c === "}" && t === "{") ||
        (c === "]" && t === "[")
      ) {
        stack.pop(); // 先出
      } else {
        return false;
      }
    }
  }
  return stack.length === 0;
};

← 树 →