/**
 * @param {string} digits
 * @return {string[]}
 */

var letterCombinations = function (digits) {
    if (digits.length === 0) return []
    const res = []
    const map = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
    const dfs = (curStr, i) => {
        if (i > digits.length - 1) {
            res.push(curStr)
            return
        }
        const letters = map[digits[i]]
        for (const l of letters) {
            dfs(curStr + l, i + 1)
        }
    }
    dfs('', 0)
    return res
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const newNums = nums1.concat(nums2).sort((a, b) => a - b)
    const len = newNums.length
    if (len % 2 === 0) {
        return (newNums[len/2 - 1] + newNums[len/2]) / 2
    } else {
        return newNums[Math.floor(len/2)]
    }
}

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
// 搜索回溯
var combinationSum = function(candidates, target) {
    const ans = []
    const dfs = (target, item, idx) => {
        if (idx === candidates.length) return
        if (target === 0) {
            ans.push(item)
            return
        }
        dfs(target, item, idx + 1)
        if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], [...item, candidates[idx]], idx)
        }
    }
    dfs(target, [], 0)
    return ans
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
// 前序遍历: 根-左-右
// 中序遍历：左-根-右
// 先用前序遍历找根节点，在用根节点去中序遍历确定左右子树
var buildTree = function(preorder, inorder) {
    // 当preorder和inorder均为空的时候说明已经到了空节点
    if (!preorder.length || !inorder.length) return null

    // 创建根节点 -> preorder[0]
    let node = new TreeNode(preorder[0])

    // 找到perorder[0]对应inorder中的位置
    let index = inorder.indexOf(preorder.shift())

    // 左右子树递归
    node.left = buildTree(preorder, inorder.slice(0, index))
    node.right = buildTree(preorder, inorder.slice(index + 1))

    // 返回根节点
    return node
}

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
// 记录该元素已使用
// 上下左右不能超边界
// 如果没找到最终值的时候恢复上一个节点的值
var exist = function(board, word) {
    // 越界处理
    board[-1] = [] // 这里处理比较巧妙，利用了js的特性
    board.push([])
    // 寻找首个字母
    for (let y = 0; y < board.length; y++) {
        for (let x = 0; x < board[0].length; x++) {
            if (word[0] === board[y][x] && dfs(word, board, y, x, 0)) return true
        }
    }
    return false
}

const dfs = function(word, board, y, x, i) {
    if (i + 1 === word.length) return true
    var tmp = board[y][x]
    // 标记该元素已使用
    board[y][x] = false
    if (board[y][x+1] === word[i+1] && dfs(word, board, y, x+1, i+1)) return true
    if (board[y][x-1] === word[i+1] && dfs(word, board, y, x-1, i+1)) return true
    if (board[y+1][x] === word[i+1] && dfs(word, board, y+1, x, i+1)) return true
    if (board[y-1][x] === word[i+1] && dfs(word, board, y-1, x, i+1)) return true
    // 回溯
    board[y][x] = tmp
}

/**
 * @param {number[]} nums
 * @return {number}
 */
// var singleNumber = function(nums) {
//     let ans = 0;
//     for(const num of nums) {
//         ans ^= num;
//     }
//     return ans;
// };

var singleNumber = function(nums) {
    return nums.reduce((pre, cur) => {
        return pre ^ cur;
    }, 0)
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 递归法实现子集枚举
// var subsets = function (nums) {
//     let result = []
//     let path = []
//     function backtracking(startIndex) {
//         result.push(path.slice())
//         for (let i = startIndex; i < nums.length; i++) {
//             path.push(nums[i])
//             backtracking(i + 1)
//             path.pop()
//         }
//     }
//     backtracking(0)
//     return result
// }

// DFS回溯思路
var subsets = function (nums) {
    const res = []
    const dfs = (index, list) => {
        res.push(list.slice())
        for (let i = index; i < nums.length; i++) {
            list.push(nums[i])
            dfs(i+1, list)
            list.pop()
        }
    }
    dfs(0, [])
    return res
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
// 队列
var levelOrder = function(root) {
    const ans = []
    if (!root) return ans
    const q = []
    q.push(root) // 初始化队列
    while (q.length) {
        const len = q.length // 当前层节点的数量
        ans.push([]) // 新的层推入数组
        for (let i = 1; i <= len; i++) {
            const node = q.shift()
            // 推入当前层的数组
            ans[ans.length - 1].push(node.val)
            // 检查左节点，存在左节点就继续加入队列
            if (node.left) q.push(node.left)
            if (node.right) q.push(node.right)
        }
    }
    return ans
}

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
// dp[i][j]是word1,word2的最小编辑距离
var minDistance = function(word1, word2) {
    let m = word1.length
    let n = word2.length
    const dp = new Array(m+1).fill(0).map(() => new Array(n+1).fill(0))
    // 初始化
    for (let i = 1; i <= m; i++) {
        dp[i][0] = i
    }
    for (let j = 1; j <= n; j++) {
        dp[0][j] = j
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i-1] === word2[j-1]) {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            }
        }
    }
    return dp[m][n]
}

/**
 * @param {number[]} height
 * @return {number}
 */
// 动态规划
var trap = function(height) {
    const n = height.length
    const left = new Array(n).fill(0)
    const right = new Array(n).fill(0)
    let ans = 0
    for (let i = 1; i < n; i++) {
        left[i] = Math.max(left[i-1], height[i-1])
    }
    for (let i = n - 2; i >= 0; i--) {
        right[i] = Math.max(right[i+1], height[i+1])

        let short = Math.min(left[i], right[i])
        if (short > height[i]) {
            ans += short - height[i]
        }
    }
    return ans
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 栈
var inorderTraversal = function(root) {
    const res = []
    let stack = []
    while (root || stack.length) {
        while (root) {
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        res.push(root.val)
        root = root.right
    }
    return res
}

/**
 * @param {number} n
 * @return {string[]}
 */
// 回溯法(DFS)
var generateParenthesis = function(n) {
    const res = []
    const backtrack = (left, right, str) => {
        if (left === n && right === n) return res.push(str)
        if (left < n) backtrack(left + 1,  right, str + '(')
        if (right < left) backtrack(left, right + 1, str + ')')
    }
    backtrack(0, 0, '')
    return res
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i]
        }
        map.set(nums[i], i)
    }
    return [-1, -1]
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
// 递归
// var mergeTwoLists = function(list1, list2) {
//     if (!list1) {
//         return list2
//     } else if (!list2) {
//         return list1
//     } else if (list1.val < list2.val) {
//         list1.next = mergeTwoLists(list1.next, list2)
//         return list1
//     } else {
//         list2.next = mergeTwoLists(list1, list2.next)
//         return list2
//     }
// }

// 迭代
var mergeTwoLists = function(list1, list2) {
    const dummy = new ListNode()
    let curr = dummy
    while (list1 && list2) {
        list1.val < list2.val
            ? [curr.next, list1] = [list1, list1.next]
            : [curr.next, list2] = [list2, list2.next]
        curr = curr.next
    }
    curr.next = list1 ?? list2
    return dummy.next
}

/**
 * @param {number[]} nums
 * @return {number}
 */
// 1.将数组元素存入set中
// 2.遍历nums，如果当前项-1存在于set，说明当前项不是连续序列的起点，忽略，继续遍历
// 3.如果当前项没有“左邻居”，它就是连续序列的起点，循环查看当前项连续的右邻居有多少个
// 4.返回最长的连续次数
var longestConsecutive = function (nums) {
    // 把数组的数字全部放入set中，一来去重，二来方便快速查找
    const set = new Set(nums)
    let max = 0
    for (let val of nums) {
        // 没有左邻居，是序列的起点，才开始数数
        if (!set.has(val - 1)) {
            let count = 1
            let now = val
            // 有右邻居，看连续的右邻居右多少个
            while (set.has(now + 1)) {
                now++
                count++
            }
            // 存放最大的连续邻居的值
            max = Math.max(max, count)
        }
    }
    return max
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s.length % 2 !== 0) return false
    const map = {
        '(' : ')',
        '{' : '}',
        '[' : ']',
    }
    let stack = []
    for (let char of s) {
        if (map[char]) {
            stack.push(map[char])
        } else {
            let ret = stack.pop()
            if (ret !== char) {
                return false   
            }
        }
    }
    return stack.length === 0
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    if (grid === null || grid.length === 0 || grid[0].length === 0) {
        return 0
    }

    let row = grid.length, col = grid[0].length

    const dp = new Array(row).fill(0).map(() => new Array(col).fill(0))
    dp[0][0] = grid[0][0]

    for (let i = 1; i < row; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }

    for (let j = 1; j < col; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j]
    }

    for (let i = 1; i < row; i++) {
        for (let j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
        }
    }

    return dp[row-1][col-1]
}

/**
 * @param {string} s
 * @return {number}
 */
// 定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。
/**
)()())

push: 一个参照物；左括号

pop：左括号，一个参照物

保持栈不能为空

[-1]
 */
const longestValidParentheses = (s) => {
    let n = s.length
    let res = 0
    let stack = [-1]
    for (let i = 0; i < n; i++) {
        let str = s[i]
        if (str === '(') {
            stack.push(i)
        } else {
            stack.pop()
            if (stack.length) {
                res = Math.max(res, i - stack[stack.length - 1])
            } else {
                stack.push(i)
            }
        }
    }
    return res
};

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
// a[i-1] a[j]
var nextPermutation = function(nums) {
    const len = nums.length
    let i = len - 2
    // 找到第一个当前项比后一项小的位置
    while (i >= 0 && nums[i] >= nums[i+1]) i--
    // i>=0，说明此时不是最大的排序
    if (i >= 0) {
        let j = len - 1
        // 找到最小的比nums[i]大的数对应的j
        while (j > i && nums[i] >= nums[j]) j--
        // 交换位置
        [nums[i], nums[j]] = [nums[j], nums[i]]
    }
    // i后面的数升序排序
    let [left, right] = [i + 1, len - 1]
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]]
        left++
        right--
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
// 动态规划
var maxSubArray = function(nums) {
    let pre = 0
    let maxAns = nums[0]
    nums.forEach((x) => {
        pre = Math.max(pre + x, x)
        maxAns = Math.max(maxAns, pre)
    })
    return maxAns
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
// 贪心
// var canJump = function(nums) {
//     // 如果只有一个，返回true
//     if (nums.length === 1) return true
//     // 记录所能到达的最大位置
//     var res = nums[0]
//     for (let i = 1; i < nums.length; i++) {
//         // 如果最大位置不能到达当前位置，则跳出
//         if (res < i) break
//         // 如果最大位置超过最后一个位置，则返回true
//         if (res >= nums.length - 1) return true
//         // 计算能到达的最大位置
//         res = res > nums[i] + i ? res : nums[i] + i
//     }
//     return false
// }

// 贪心
var canJump = function(nums) {
    let n = nums.length - 1
    let maxLen = 0
    for (let i = 0; i <= maxLen; i++) {
        maxLen = Math.max(maxLen, nums[i] + i)
        if (maxLen >= n) return true
    }
    return false
}

// 动态规划
// var canJump = function(nums) {
//     let end = nums.length - 1

//     for (let i = nums.length - 2; i >= 0; i--) {
//         if (end - i <= nums[i]) {
//             end = i
//         }
//     }

//     return end === 0
// }

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map()
    for (let str of strs) {
        let array = Array.from(str)
        array.sort()

        let key = array.toString()
        let list = map.get(key) ? map.get(key) : []
        list.push(str)

        map.set(key, list)
    }
    return Array.from(map.values())
};

/**
 * @param {number[]} prices
 * @return {number}
 */
// 买入卖出各一次
//  贪心
// var maxProfit = function(prices) {
//     if (prices.length === 0) return 0

//     let min = prices[0]
//     let max = 0

//     for (let p of prices) {
//         min = Math.min(min, p)
//         max = Math.max(max, p - min)
//     }

//     return max
// }

// 动态规划 时间复杂度O(n) 空间复杂度O(n)，dp数组第二维是常数
var maxProfit = function(prices) {
    let n = prices.length
    let dp = new Array(n).fill(0).map(() => 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]
}

// 压缩空间
// var 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]
// }

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 * 快慢指针法
 */
var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode(-1, head)
    let [slow, fast] = [dummy, dummy]

    for (let i = 0; i <= n; i++) {
        fast = fast.next
    }

    while (fast) {
        slow = slow.next
        fast = fast.next
    }

    slow.next = slow.next.next

    return dummy.next
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 * 递归合并链表+两两合并
 */
var mergeKLists = function(lists) {
    if (!lists.length) return null
    function merge(l1, l2) {
        if (!l1) return l2
        if (!l2) return l1
        if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2)
            return l1
        } else {
            l2.next = merge(l1, l2.next)
            return l2
        }
    }
    return lists.reduce((pre, cur) => merge(pre, cur))
}

/**
 * @param {number[]} heights
 * @return {number}
 */
// 分治法
// 从高度值最小的高度的最大面积 (end-start+1) * height[min]，将该面积与高度最小的柱子左边和右边形成的最大面积来比较。分治的最后是每一个矩形的面积。

const largestRectangleArea = (heights) => {
    let maxArea = 0
    const stack = [] // 单调递增栈 注意栈存的是下标
    heights = [0, ...heights, 0] // 在heights数组前后增加哨兵 用来清零单调递增栈里的元素
    for (let i = 0; i < heights.length; i++) {
        // 当前元素对应的高度小于栈顶元素对应的高度时
        while (heights[i] < heights[stack[stack.length - 1]]) {
            const stackTopIndex = stack.pop() // 出栈
            maxArea = Math.max( // 计算面积 并更新最大面积
                maxArea,
                heights[stackTopIndex] * (i - stack[stack.length - 1] - 1) // 高乘宽
            )
        }
        stack.push(i) // 当前下标加入栈
    }
    return maxArea
}

/**
 * @param {number[]} nums
 * @return {void}
 * 
 */
// 遇到0，把0放在数组最前方，此时i位置没变，不用处理
// 遇到2，把2放在数组最后放，此时i向后偏移了1，需要进行i--，然后数组末尾的2已经被统计过了，所以len可以对应再减1，避免重复的问题

var sortColors = function(nums) {
    let len = nums.length
    for (let i = 0; i < len; i++) {
        if (nums[i] === 0) {
            nums.splice(i, 1)
            nums.unshift(0)
        } else if (nums[i] === 2) {
            nums.splice(i, 1)
            nums.push(2)
            len--
            i--
        }
    }
}

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
// 动态规划
// dp[i]: 子串s[0, i]是否满足，为boolean
// dp[i]初始化：除了dp[0]为true，其他为false
// 从0到n遍历字符串，判断当前dp[i]含义是否满足
// 在判断当前dp[i]中，从0到i遍历分隔点j
// 1.若[0,j]满足，且剩下的在wordDict中出现过，则当前[0,i]子串就满足
// 2.若当前[0,i]子串满足，就不用继续遍历当前子串的分隔点了，跳过，判断下一轮子串[0, i+1]
const wordBreak = (s, wordDict) => {
    const n = s.length
    const set = new Set(wordDict)
    // dp初始化，除了第一个，全为false
    const dp = new Array(n + 1).fill(false)
    dp[0] = true

    // 从1到n遍历s
    for (let i = 1; i <= n; i++) {
        // 当遍历到i时，再从0到i遍历
        for (let j = 0; j < i; j++) {
            // 当前i所处的子串是否可以，取决于分隔点j
            // 对于分隔点j，若[0,j]满足，且剩下的在wordDict中出现过，则当前[0,i]子串就满足
            if (dp[j] && set.has(s.slice(j , i))) {
                dp[i] = true
                // 若当前[0, i] 子串满足，就不用继续遍历当前子串的分隔点了
                // 跳过，判断下一轮子串[0,i+1]
                break
            }
        }
    }
    return dp[n]
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
// 最大路径和为根节点+左子树+右子树的深度最大值
// 当前节点往下走的最大值分三种情况：
// 1. 往左走：当前节点+L(左子树的最大深度)
// 2. 往右走：当前节点+R(右子树的最大深度)
// 3. 不走：当前节点如果为负值，直接舍弃返回0
var maxPathSum = function(root) {
    let ans = -Infinity
    dfs(root)
    return ans

    // 从当前节点往下走
    function dfs(root) {
        // 根节点为空直接返回0
        if (!root) return 0
        // 遍历左子树的深度
        let left = dfs(root.left)
        // 遍历右子树的深度
        let right = dfs(root.right)
        // 更新路径的最大值
        ans = Math.max(ans, root.val + left + right)
        // 返回从当前节点往下走的最大值
        return Math.max(0, Math.max(left, right) + root.val)
    }
}

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
// 使用辅助数组
// 对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。
// matrix[row][col] matrix_new[col][n-row-1]
var rotate = function(matrix) {
    const n = matrix.length
    const matrix_new = new Array(n).fill(0).map(() => new Array(n).fill(0))

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            matrix_new[j][n-1-i] = matrix[i][j]
        }
    }

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            matrix[i][j] = matrix_new[i][j]
        }
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let max = ''
    
    for (let i = 0; i < s.length; i++) {
        helper(i, i)
        helper(i, i+1)
    }

    function helper(l, r) {
        while(l >= 0 && r < s.length && s[l] === s[r]) {
            l--
            r++
        }
        const maxStr = s.slice(l + 1, r - 1 + 1)
        if (maxStr.length > max.length) max = maxStr
    }

    return max
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
// 栈
var isValidBST = function(root) {
    let stack = []
    let inorder = -Infinity
    while (root || stack.length) {
        while (root) {
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        if (root.val <= inorder) {
            return false
        }
        inorder = root.val
        root = root.right
    }
    return true
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

var threeSum = function(nums) {
    let ans = []
    const len = nums.length
    if (nums === null || len < 3) return ans
    nums.sort((a, b) => a - b)

    for (let i = 0; i < nums.length; i++) {
        if (nums[0] > 0) break
        if (i > 0 && nums[i] === nums[i - 1]) continue
        let l = i + 1
        let r = len - 1
        while (l < r) {
            const sum = nums[i] + nums[l] + nums[r]
            if (sum === 0) {
                ans.push([nums[i], nums[l], nums[r]])
                while(l < r && nums[l] === nums[l+1]) l++
                while(l < r && nums[r] === nums[r-1]) r--
                l++
                r--
            }
            else if (sum < 0) l++
            else if (sum > 0) r--
        }
    }

    return ans
}

/**
 * @param {number} n
 * @return {number}
 * 题目分析:
 * 第1级台阶：1种方法（爬1级）
 * 第2级台阶：2种方法（爬1级或爬2级）
 * 第n级台阶：dp[i] = dp[i-1] + dp[i-2]
 */
// 动态规划
// 滚动数组**
// var climbStairs = function(n) {
//     if (n === 1) return 1
//     if (n === 2) return 2
//     let [pre, cur, sum] = [1, 1, 2]
//     for (let i = 3; i <= n; i++) {
//         [pre, cur] = [cur, sum]
//         sum = pre + cur
//     }
//     return sum
// }

var 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]
}

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if (matrix.length === 0) return 0

    let res = 0
    let heights = new Array(matrix[0].length).fill(0) // 初始化heights数组
    for (let row = 0; row < matrix.length; row++) {
        for (let col = 0; col < matrix[0].length; col++) {
            if (matrix[row][col] === '1') heights[col] += 1
            else heights[col] = 0
        } // 求出每一层的 heights[] 然后传给 largestRectangleArea 函数
        res = Math.max(res, largestRectangleArea(heights)) // 更新一下最大矩形面积
    }
    return res
};

const largestRectangleArea = (heights) => {
    let maxArea = 0
    const stack = [] // 单调递增栈 注意栈存的是下标
    heights = [0, ...heights, 0] // 在 heights 数组前后增加两个哨兵 用来清零单调递增栈里的元素
    for (let i = 0; i < heights.length; i++) {
        // 当前元素对应的高度小于栈顶元素对应的高度时
        while (heights[i] < heights[stack[stack.length - 1]]) {
            const stackTopIndex = stack.pop() // 出栈
            maxArea = Math.max(
                maxArea,
                heights[stackTopIndex] * (i - stack[stack.length - 1] - 1) // 高乘宽
            )
        }
        stack.push(i) // 当前下标加入栈
    }
    return maxArea
}

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const set = new Set()
    let [l, r, maxLen] = [0, 0, 0]
    while(r < s.length) {
        set.has(s[r]) ? set.delete(s[l++]) : set.add(s[r++])
        maxLen = Math.max(maxLen, set.size)
    }
    return maxLen
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 * 二分搜索
 * 关键字：排序，搜索
 */
var search = function(nums, target) {
    let [left, right] = [0, nums.length - 1]

    while (left <= right) {
        const mid = (left + right) >>> 1
        if (nums[mid] === target) return mid

        if (nums[mid] > nums[right]) {
            if (nums[left] <= target && nums[mid] > target) right = mid - 1
            else left = mid + 1
        } else {
            if (nums[mid] < target && nums[right] >= target) left = mid + 1
            else right = right - 1
        }
    }
    return -1
}

/**
 * @param {number} n
 * @return {number}
 */
// 数学
var numTrees = function(n) {
    let res = 1
    for (let i = 1; i < n; i++) {
        res = res * 2 * (2 * i + 1) / (i + 2)
    }
    return res
}

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
// 将需要匹配的字符放入字典表，存储结构为需要匹配的字符，以及字符出现的次数：[字符，次数]
// 利用双指针维护一个滑动窗口，不断移动右指针
// 判断右指针的字符是否与字典表中的匹配
// 是：将字典表中的次数-1，直到为0 （创建一个needType）记录需要匹配的字符数量，初始长度为Map的size，当对应的字符次数为0时，就减1
// 否：继续移动右指针
// 当needType的值为0时，就证明在当前窗口所有字符都匹配成功了
// 1.移动左指针，缩小滑动窗口的大小
// 2.移动过程中判断左指针指向的值是否为字典中值，如果是就证明匹配的值少了一个，这个需要更新Map中的次数，以及needType的数量
// 3.记录每次窗口中的字符，找到最小的返回
var minWindow = function(s, t) {
    // 创建左指针
    let l = 0
    // 创建右指针
    let r = 0
    // 最后需要返回的最小长度子串
    let res = ''
    // 创建字典表
    const m = new Map()
    // 遍历需要匹配的字符
    for (let i = 0; i < t.length; i++) {
        const c = t[i]
        // 放入字典表
        m.set(c, m.has(c) ? m.get(c) + 1 : 1)
    }
    // 创建记录需要匹配的字符种类
    let needType = m.size
    // 遍历字符串
    while (r < s.length) {
        // 获取当前字符
        const c = s[r]
        // 如果是需要匹配的字符
        if (m.has(c)) {
            // 更新字典表中的次数-1
            m.set(c, m.get(c) - 1)
            // 如果次数为0，证明这个字符种类在当前窗口已经集齐了，needType-1
            if (m.get(c) === 0) needType -= 1
        }
        // 当needType为0，证明所有需要匹配的字符串都已经在当前滑动窗口中
        while (needType === 0) {
            const c2 = s[l]
            // 记录当前滑动窗口的字符
            let newRes = s.slice(l, r + 1)
            // 当新的窗口中字符长度小于上次的字符长度时，更新结果
            // !res 是在结构值为空的时候需要更新一下第一次匹配的值
            if (!res || newRes.length < res.length) res = newRes
            // 如果左指针移动过程中出现，字典中的值证明需要匹配的字符已经脱离了当前窗口
            if (m.has(c2)) {
                // 更新表中需要出现的次数
                m.set(c2, m.get(c2) + 1)
                // 更新needType
                if (m.get(c2) === 1) needType += 1
            }
            // 移动左指针
            l++
        }
        // 移动右指针
        r++
    }
    // 返回结果值
    return res
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let [start, end] = [0, nums.length - 1]

    while (start <= end) {
        const mid = (start + end) >>> 1
        if (nums[mid] === target) {
            [start, end] = [mid, mid]
            break
        }
        nums[mid] > target ? (end = mid - 1) : (start = mid + 1)
    }

    while (nums[start - 1] === target) start --
    while (nums[end + 1] === target) end++

    return start > end ? [-1, -1] : [start, end]
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
// 1. 先用两个变量把原先的左右子树保持起来
// 2. 将左子树作为右子树
// 3. 将原先的右子树接到当前右子树的末端
// 递归
var flatten = function(root) {
    // 递归终止
    if (root === null) return

    // 分别递归左右节点
    const left = root.left
    const right = root.right
    flatten(left)
    flatten(right)

    // 将树的right节点替换为left节点
    root.right = root.left
    root.left = null

    // 循环 找到最右的节点
    while (root.right) root = root.right
    // 最右的节点 指向right节点
    root.right = right
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode()
    let curr = dummy
    let carry = 0

    while(l1 || l2) {
        const x = l1 ? l1.val : 0
        const y = l2 ? l2.val : 0

        const total = x + y + carry
        curr.next = new ListNode(total % 10)
        curr = curr.next
        carry = Math.floor(total / 10)

        if (l1) l1 = l1.next
        if (l2) l2 = l2.next
    }
    if (carry) curr.next = new ListNode(carry)

    return dummy.next
}