geekhyt / javascript-leetcode Goto Github PK

const addStrings = (num1, num2) => {
  while (num1.length > num2.length) num2 = '0' + num2
  while (num1.length < num2.length) num1 = '0' + num1
  let res = '', carry = 0;
  for (let i = num1.length - 1; i >= 0; i--) {
    const sum = +num1[i] + +num2[i] + carry 
    res = sum % 10 + res                       
    carry = sum > 9 ? 1 : 0
  }
  return carry === 1 ? '1' + res : res
};

const maxArea = function(height) {
    let max = 0 // 最大容纳水量
    for (let i = 0; i < height.length; i++) {
        for (let j = i + 1; j < height.length; j++) {
            // 当前容纳水量
            let cur = (j - i) * Math.min(height[i], height[j])
            if (cur > max) {
                max = cur
            }
        }
    }
    return max
}

const maxArea = function(height) {
    let max = 0 // 最大容纳水量
    let left = 0 // 左指针
    let right = height.length - 1 // 右指针
    
    while (left < right) {
        // 当前容纳水量
        let cur = (right - left) * Math.min(height[left], height[right]);
        max = Math.max(cur, max)
        height[left] < height[right] ? left ++ : right --
    }

    return max
};

const preorderTraversal = function(root) {
    const result = [];
    function pushRoot(node){
        if (node !== null) {
            result.push(node.val);
            if (node.left !== null){ 
                pushRoot(node.left);
            }
            if (node.right !== null) {
                pushRoot(node.right);
            } 
        }
    }
    pushRoot(root);
    return result;
};

const maxDepth = function(root) {
    if (!root) { // 递归终止条件
        return 0
    } else {
        const left = maxDepth(root.left)
        const right = maxDepth(root.right)
        return Math.max(left, right) + 1
    }
};

const maxDepth = function(root) {
    let depth = 0
    if (root === null) {
        return depth
    }
    const queue = [root]
    while (queue.length) {
        let len = queue.length
        while (len--) {
            const cur = queue.shift()
            cur.left && queue.push(cur.left)
            cur.right && queue.push(cur.right)
        }
        depth++
    }
    return depth
};

const permuteUnique = function(nums) {
    const len = nums.length, res = [], used = []
    nums.sort((a, b) => a - b)
    const backtrack = (deepStack) => {
        if (deepStack.length === len) {
            res.push(deepStack.slice())
            return
        }
        for (let i = 0; i < len; i++) {
            // 当前选项与上一项相同、且上一项存在、且没有被使用过，则忽略
            if (nums[i - 1] === nums[i] && i - 1 >= 0 && !used[i - 1]) continue 
            if (used[i]) continue // 使用过便不再使用
            deepStack.push(nums[i])
            used[i] = true
            backtrack(deepStack)
            deepStack.pop()
            used[i] = false
        }
    }
    backtrack([])
    return res
}

const letterCombinations = function (digits) {
    if (!digits) {
        return []
    }
    const len = digits.length
    const map = new Map()
    map.set('2', 'abc')
    map.set('3', 'def')
    map.set('4', 'ghi')
    map.set('5', 'jkl')
    map.set('6', 'mno')
    map.set('7', 'pqrs')
    map.set('8', 'tuv')
    map.set('9', 'wxyz')
    const result = []

    function generate(i, str) {
        if (i === len) {
            result.push(str)
            return
        }
        const tmp = map.get(digits[i])
        for (let r = 0; r < tmp.length; r++) {
            generate(i + 1, str + tmp[r])
        }
    }
    generate(0, '')
    return result
}

const maxSubArray = function(nums) {
    const len = nums.length
    const dp = new Array(len).fill(1)
    dp[0] = nums[0]
    let res = dp[0]
    for (let i = 1; i < len; i++) {
        if (dp[i - 1] > 0) {
            dp[i] = dp[i - 1] + nums[i]
        } else {
            dp[i] = nums[i]
        }
        res = Math.max(res, dp[i])
    }
    return res
}

const maxSubArray = function(nums) {
    let res = nums[0]
    let cur = 0
    for (const num of nums) {
        if (cur > 0) {
            cur += num
        } else {
            cur = num
        }
        res = Math.max(res, cur)
    }
    return res
}

const permute = function(nums) {
    const len = nums.length, res = [], deepStack = []
    const backtrack = (deepStack) => {
        // 递归终止条件
        if (deepStack.length == len) {
            return res.push(deepStack)
        }
        for (let i = 0; i < len; i++) {
            // 已经选择过的数字不能再做选择
            if (!deepStack.includes(nums[i])) {
                deepStack.push(nums[i]) // 做选择
                backtrack(deepStack.slice())
                deepStack.pop() // 撤销选择
            }
        }
    }
    backtrack(deepStack)
    return res
}

dp[i][k][0]
dp[i][k][1]

// 举个🌰
dp[2][2][1] // 今天是第 2 天，手中持有股票，最多还可以进行 2 次交易

// 今天手中没有持有股票，有两种可能：
// 1. 昨天没有持有，今天选择不操作。 对应: dp[i - 1][k][0]
// 2. 昨天持有，今天卖出了，所以今天没有股票了。对应: dp[i - 1][k][1] + prices[i]
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])


// 今天手中持有股票，有两种可能：
// 1. 昨天手中持有股票，今天选择不操作。对应: dp[i - 1][k][1]
// 2. 昨天没有持有股票，今天买入了。对应: dp[i - 1][k - 1][0] - prices[i]
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])
// k = 0 时，dp[i - 1][0][0] = 0

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], -prices[i])

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i])
    }
    return dp[n - 1][0]
}

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], -prices[i])
    }
    return dp[0]
}

const maxProfit = function(prices) {
    let n = prices.length
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < n; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in,  -prices[i])
    }
    return profit_out
}

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0 
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
    }
    return dp[n - 1][0]
}

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        let tmp = dp[0] // 中间变量可省略，因为当天买入卖出不影响结果
        dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], tmp - prices[i])
    }
    return dp[0]
}

const maxProfit = function(prices) {
    let n = prices.length
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < n; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

for (let i = 0; i < n; i++) {
    for (let k = maxK; k >= 1; k--) {
        dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
        dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
    }
}

dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])

const maxProfit = function(prices) {
    let n = prices.length
    let dp_i10 = 0
    let dp_i11 = -prices[0]
    let dp_i20 = 0
    let dp_i21 = -prices[0]
    for (let i = 1; i < n; i++) {
        dp_i20 = Math.max(dp_i20, dp_i21 + prices[i])
        dp_i21 = Math.max(dp_i21, dp_i10 - prices[i])
        dp_i10 = Math.max(dp_i10, dp_i11 + prices[i])
        dp_i11 = Math.max(dp_i11, -prices[i])
    }
    return dp_i20
}

const maxProfit = function(prices) {
    let profit_1_in = -prices[0], profit_1_out = 0
    let profit_2_in = -prices[0], profit_2_out = 0
    let n = prices.length
    for (let i = 1; i < n; i++) {
        profit_2_out = Math.max(profit_2_out, profit_2_in + prices[i])
        profit_2_in = Math.max(profit_2_in, profit_1_out - prices[i])
        profit_1_out = Math.max(profit_1_out, profit_1_in + prices[i])
        profit_1_in = Math.max(profit_1_in, -prices[i])
    }
    return profit_2_out
}

const maxProfit = function(k, prices) {
    let n = prices.length
    const maxProfit2 = function(prices) {
        let profit_out = 0
        let profit_in = -prices[0]
        for (let i = 1; i < n; i++) {
            profit_out = Math.max(profit_out, profit_in + prices[i])
            profit_in = Math.max(profit_in, profit_out - prices[i])
        }
        return profit_out
    }
    if (k > n / 2) {
        return maxProfit2(prices)
    }
    let profit = new Array(k)
    // 初始化买入卖出时的利润，将每次交易买入、卖出时的利润放在一个对象中，实现降维
    for (let j = 0; j <= k; j++) {
        profit[j] = {
            profit_in: -prices[0],
            profit_out: 0
        }
    }
    for (let i = 0; i < n; i++) {
        for (let j = 1; j <= k; j++) {
            profit[j] = {
                profit_out: Math.max(profit[j].profit_out, profit[j].profit_in + prices[i]), 
                profit_in: Math.max(profit[j].profit_in, profit[j-1].profit_out - prices[i])
            }
        }
    }
    return profit[k].profit_out
}

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 2][k][0] - prices[i])

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i])

const maxProfit = function(prices) {
    let n = prices.length
    let dp_i0 = 0
    let dp_i1 = -prices[0];
    let dp_pre = 0 // 代表 dp[i-2][0]
    for (let i = 0; i < n; i++) {
        let tmp = dp_i0
        dp_i0 = Math.max(dp_i0, dp_i1 + prices[i])
        dp_i1 = Math.max(dp_i1, dp_pre - prices[i])
        dp_pre = tmp
    }
    return dp_i0
}

const maxProfit = function(prices) {
    let n = prices.length
    let profit_in = -prices[0]
    let profit_out = 0
    let profit_freeze = 0
    for (let i = 1; i < n; i++) {
        let temp = profit_out
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_freeze - prices[i])
        profit_freeze = temp
    }
    return profit_out
}

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

const maxProfit = function(prices, fee) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        let tmp = dp[0]
        dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee)
        dp[1] = Math.max(dp[1], tmp - prices[i])
    }
    return dp[0]
}

const maxProfit = function(prices, fee) {
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i] - fee)
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}

const isSameTree = function(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

const lengthOfLIS = function(nums) {
    let n = nums.length
    if (n == 0) {
        return 0
    }
    let dp = new Array(n).fill(1)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp) 
}

const lengthOfLIS = function(nums) {
    let len = nums.length
    if (len <= 1) {
        return len
    }
    let tails = [nums[0]]
    for (let i = 0; i < len; i++) {
        // 当前遍历元素 nums[i] 大于 前一个递增子序列的 尾元素时，追加到后面即可
        if (nums[i] > tails[tails.length - 1]) {
            tails.push(nums[i])
        } else {
            // 否则，查找递增子序列中第一个大于当前值的元素，用当前遍历元素 nums[i] 替换它
            // 递增序列，可以使用二分查找
            let left = 0
            let right = tails.length - 1
            while (left < right) {
                let mid = (left + right) >> 1;
                if (tails[mid] < nums[i]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            tails[left] = nums[i]
        }
    }
    return tails.length
}

const removeDuplicates = function(nums) {
    const n = nums.length
    let i = 0
    if (n === 0) return 0
    for (let j = 1; j < n; j++) {
        if (nums[j] !== nums[j - 1]) {
            i++
            nums[i] = nums[j]
        }
    }
    return i + 1
}

const longestPalindrome = function (s) {
    const len = s.length
    const dp = Array.from(new Array(len), () => new Array(len).fill(0))
    let res = ''
    for (let i = len - 1; i >= 0; i--) {
        for (let j = i; j < len; j++) {
            dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])
            if (dp[i][j] && j - i + 1 > res.length) { // 符合条件时截取得到最长的回文串
                res = s.slice(i, j + 1)
            }
        }
    }
    return res
}

const mergeSort = function(arr) {
    const merge = (right, left) => {
    const result = []
    let i = 0, j = 0
    while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
        result.push(left[i++])
      } else {
        result.push(right[j++])
      }
    }
    while (i < left.length) {
      result.push(left[i++])
    }
    while (j < right.length) {
      result.push(right[j++])
    }
    return result
    }
    const sort = (arr) => {
        if (arr.length === 1) { return arr }
        const mid = Math.floor(arr.length / 2)
        const left = arr.slice(0, mid)
        const right = arr.slice(mid, arr.length)
        return merge(mergeSort(left), mergeSort(right))
    }
    return sort(arr)
}

const threeSum = function(nums) {
    const result = []
    const len = nums.length
    if (len < 3) {
        return result
    }
    nums.sort((a, b) => a - b)
    for (let i = 0; i < len - 2; i++) {
        if (nums[i] > 0) {
            break
        }
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue
        }
        let L = i + 1
        let R = len - 1
        while (L < R) {
            let sum = nums[i] + nums[L] + nums[R]
            if (sum === 0) {
                result.push([nums[i], nums[L], nums[R]])
                while(nums[L] === nums[L + 1]){
                    L++
                }
                while(nums[R] === nums[R - 1]){
                    R--
                }
                L++
                R--
            } else if (sum < 0) {
                L++
            } else {
                R--
            }
        }
    }
    return result
}

const longestValidParentheses = function(s) {
  let res = 0
  const len = s.length
  const dp = new Array(len).fill(0)
  for (let i = 1; i < len; i++) {
    if (s[i] == ')') {
      if (s[i - 1] == '(') {
        if (i - 2 >= 0) {
          dp[i] = dp[i - 2] + 2
        } else {
          dp[i] = 2
        }
      } else if (s[i - dp[i - 1] - 1] == '(') {
        if (i - dp[i - 1] - 2 >= 0) {
          dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
        } else {
          dp[i] = dp[i - 1] + 2
        }
      }
    }
    res = Math.max(res, dp[i])
  }
  return res
}

const removeNthFromEnd = function(head, n) {
    let prev = new ListNode(0), fast = prev, slow = prev;
    prev.next = head;
    while (n--) {
        fast = fast.next;
    }
    while (fast && fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return prev.next;
}

const MinStack = function() {
    this.stack = [];
    this.resStack = [Infinity];
};

MinStack.prototype.push = function(x) {
    this.stack.push(x);
    this.resStack.push(Math.min(this.resStack[this.resStack.length - 1], x));
};

MinStack.prototype.pop = function() {
    this.stack.pop();
    this.resStack.pop();
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function() {
    return this.resStack[this.resStack.length - 1];
};

const isSymmetric = function(root) {
    if (root === null) return true
    return isEqual(root.left, root.right) // 比较左右子树是否对称
};

const isEqual = function(left, right) {
    // 递归终止条件
    if (left === null && right === null) return true // 对称
    if (left === null || right === null) return false // 不对称
    // 比较左右子树的 root 值以及左右子树是否对称
    return left.val === right.val
        && isEqual(left.left, right.right)
        && isEqual(left.right, right.left)
}

const quickSort = function(arr) {
    const quick = function(arr) {
        if (arr.length <= 1) return arr
        const len = arr.length
        const index = Math.floor(len >> 1)
        const pivot = arr.splice(index, 1)[0]
        const left = []
        const right = []
        for (let i = 0; i < len; i++) {
            if (arr[i] > pivot) {
                right.push(arr[i])
            } else if (arr[i] <= pivot) {
                left.push(arr[i])
            }
        }
        return quick(left).concat([pivot], quick(right))
    }
    const result = quick(arr)
    return result
}

const plusOne = function(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] === 9) {
            digits[i] = 0
        } else {
            digits[i]++
            return digits
        }
    }
    digits.unshift(1)
    return digits
};

const subsets = function(nums) => {
    const res = []
    const dfs = function(start, cur) {
        if (start === nums.length) {
            res.push(cur.slice())
            return
        }
        cur.push(nums[start]) // 选择
        dfs(start + 1, cur)
        cur.pop()
        dfs(start + 1, cur) // 不选择
    }
    dfs(0, [])
    return res
}

const invertTree = function(root) {
    if (root === null) return null // 递归终止条件
    invertTree(root.left)
    invertTree(root.right)
    const temp = root.left
    root.left = root.right
    root.right = temp
    return root
}

const invertTree = function(root) {
    if (root === null) return null // 递归终止条件
    const temp = root.left
    root.left = root.right
    root.right = temp
    invertTree(root.left)
    invertTree(root.right)
    return root
}

const invertTree = (root) => {
  if (root === null) return null;
  const queue = [root];
  while (queue.length) {
    const cur = queue.shift();
    [cur.left, cur.right] = [cur.right, cur.left];
    if (cur.left) queue.push(cur.left);
    if (cur.right) queue.push(cur.right);
  }
  return root;
}

const largestRectangleArea = function(heights) {
  let maxArea = 0
  let len = heights.length
  for (let i = 0; i < len; i++) {
    let minHeight = heights[i]
    for (let j = i; j < len; j++) {
      minHeight = Math.min(minHeight, heights[j])
      maxArea = Math.max(maxArea, minHeight * (j - i + 1))
    }
  }
}

const largestRectangleArea = function(heights) {
  let maxArea = 0
  let len = heights.length
  for (let i = 0; i < len; i++) {
    let left = i
    let right = i
    while (left >= 0 && heights[left] >= heights[i]) {
      left--
    }
    while (right < len && heights[right] >= heights[i]) {
      right++
    }
    maxArea = Math.max(maxArea, (right - left - 1) * heights[i])
  }
  return maxArea
}

const largestRectangleArea = function(heights) {
  let maxArea = 0
  let stack = []
  heights.push(0)
  heights.unshift(0)
  // heights = [0, ...heights, 0] 你也可以这样写
  for (let i = 0; i < heights.length; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
      maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack[stack.length - 1] - 1))
    }
    stack.push(i)
  }
  return maxArea
}

const climbStairs = function(n) {
    const dp = []
    dp[0] = 1
    dp[1] = 1
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

const climbStairs = function(n) {
    let a1 = 1
    let a2 = 1
    for (let i = 2; i <= n; i++) {
        [a1, a2] = [a2, a1 + a2]
    }
    return a2
}

const insertSort = function(arr) {
    const len = arr.length
    let curr, prev
    for (let i = 1; i < len; i++) {
        curr = arr[i]
        prev = i - 1
        while (prev >= 0 && arr[prev] > curr) {
            arr[prev + 1] = arr[prev]
            prev--
        }
        arr[prev + 1] = curr
    }
    return arr
}

const isValid = function(s) {
    // 奇数个括号或右括号开头的情况无效
    if (s.length % 2 !== 0 || [')', ']', '}'].indexOf(s[0]) !== -1) return false
    const map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    const stack = []
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
            stack.push(s[i])
        } else if(s[i] !== map[stack.pop()]){
            return false
        }
    }
    return stack.length === 0
}