/**
 * 推荐写法，优化空间
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  // 动态规划自底向上计算，从最小层级开始计算
  let arr = new Array(n + 1)

  if (n == 1) return 1
  if (n == 2) return 2

  let a = 1
  let b = 2
  let res = 0

  for (let i = 3; i <= n; i++) {
    res = a + b
    a = b
    b = res
  }

  return res
}

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n == 1) return 1
  if (n == 2) return 2

  let dp = []
  dp[1] = 1
  dp[2] = 2
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }

  return dp[n]
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  // 动态规划的题目都要手动推导一遍，找出规律
  if (nums.length == 1) return nums[0]
  if (nums.length == 2) return Math.max(nums[0], nums[1])
  let max = []
  max[0] = nums[0]
  max[1] = Math.max(nums[0], nums[1])
  for (let i = 2; i < nums.length; i++) {
    max[i] = Math.max(max[i - 1], max[i - 2] + nums[i])
  }

  return max[nums.length - 1]
}

function minCostClimbingStairs(cost):
    n = length of cost

    dp[0] = 0  // 到达第0阶（起点）不花钱
    dp[1] = 0  // 到达第1阶（也可作为起点）不花钱

    for i from 2 to n:
        // 你可以从 i-1 跨一步，或者从 i-2 跨两步
        dp[i] = min(
            dp[i - 1] + cost[i - 1],
            dp[i - 2] + cost[i - 2]
        )

    return dp[n]

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  // 求最小花费 + 每次可以跨1或者2个台阶
  // ==> 求到最后一个台阶的花费
  // ==> 倒数第二个台阶+到倒数第二个台阶的花费  ~ 倒数第一个台阶+到倒数第一个台阶的花费
  // ==> 求两个花费得最小值
  if (cost.length <= 1) return 0

  let min = []
  min[0] = 0
  min[1] = 0
  min[2] = Math.min(cost[0], cost[1])

  for (let i = 3; i <= cost.length; i++) {
    min[i] = Math.min(min[i - 2] + cost[i - 2], min[i - 1] + cost[i - 1])
  }
  // console.log({ min, target: min[cost.length] })
  return min[cost.length]
}

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  if (cost.length <= 1) return 0

  let min = [0, 0] // 0 1 位置的最小花费都是 0
  for (let i = 2; i <= cost.length; i++) {
    min[i] = Math.min(min[i - 2] + cost[i - 2], min[i - 1] + cost[i - 1])
  }

  return min[cost.length]
}

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  if (cost.length <= 1) return 0

  let prev = 0 // dp[i-2]
  let curr = 0 // dp[i-1]
  for (let i = 2; i <= cost.length; i++) {
    const next = Math.min(prev + cost[i - 2], curr + cost[i - 1])
    prev = curr
    curr = next
  }

  return curr
}

函数 Tribonacci(n):
    如果 n 等于 0，返回 0
    如果 n 小于 3，返回 1

    初始化数组 prev 为 [0, 1, 1]

    从 i = 3 到 n，进行以下操作：
        prev[i] = prev[i - 3] + prev[i - 2] + prev[i - 1]

    返回 prev[n]

/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function (n) {
  if (n == 0) return 0
  if (n < 3) return 1
  let prev = [0, 1, 1]
  for (let i = 3; i <= n; i++) {
    prev[i] = prev[i - 3] + prev[i - 2] + prev[i - 1]
  }
  return prev[n]
}

函数 rob(nums):
    如果只有 1 个房子：
        返回它的钱

    情况一：偷第 0 到 n-2 号房子（不偷最后一间）
    情况二：偷第 1 到 n-1 号房子（不偷第一间）

    分别计算这两种情况的最大偷盗金额：
        max1 = 偷[0, n-2] 之间的最大金额
        max2 = 偷[1, n-1] 之间的最大金额

    返回 max(max1, max2)

函数 偷[start, end]:
    dp[i] 表示偷到第 i 间房子为止，最多偷到多少钱

    dp[start] = nums[start]
    dp[start + 1] = max(nums[start], nums[start + 1])

    从 i = start + 2 到 end：
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    返回 dp[end]

/**
 * 小偷专用函数：打家劫舍 II（房子围成一圈）
 * @param {number[]} nums - 每间房子的现金列表
 * @return {number} - 最多能偷到多少钱
 */
var rob = function (nums) {
  /**
   * 小偷的助手函数：负责在一条直线上的房子里偷东西
   * @param {number[]} nums - 所有房子里的现金
   * @param {number} start - 从第几个房子开始
   * @param {number} end - 偷到第几个房子结束
   * @return {number} - 从 start 到 end 之间最多能偷多少钱
   */
  function rob_item(nums, start, end) {
    // 如果房子是空的，啥都偷不到
    if (nums.length == 0) return 0

    // 如果只有一个房子，那就直接偷它！
    if (nums.length == 1) return nums[0]

    // 如果 start 和 end 是同一个房子，就只能偷这一家
    if (start == end) return nums[start]

    // 创建一个记账本 dp，用来记每一步最多能偷多少钱
    let dp = []

    // 第一个能偷的房子是 start，把它偷了
    dp[start] = nums[start]

    // 第二个房子是 start+1，这时我们要选：偷 start 还是 start+1，谁钱多偷谁
    dp[start + 1] = Math.max(nums[start], nums[start + 1])

    // 从第三个房子开始（也就是 start + 2），我们一个一个往后看
    for (let i = start + 2; i <= end; i++) {
      // 有两个选择：
      // 1. 不偷这一家，那就保持前一个的偷法（dp[i - 1]）
      // 2. 偷这一家，那前一家不能偷，所以是 dp[i - 2] + nums[i]
      // 然后比较这两个选项，选钱多的那个
      dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
    }

    // 最后返回偷到第 end 家时最多能偷多少钱
    return dp[end]
  }

  const len = nums.length - 1

  // 特别情况：如果只有一间房子，那直接偷它就好
  if (nums.length === 1) return nums[0]

  // 情况一：不偷最后一家 → 偷第 0 到 len-1 家
  const max1 = rob_item(nums, 0, len - 1)

  // 情况二：不偷第一家 → 偷第 1 到 len 家
  const max2 = rob_item(nums, 1, len)

  // 比较两个方案哪个偷的钱更多，返回最多的那个
  const res = Math.max(max1, max2)

  return res
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var deleteAndEarn = function (nums) {
  // 1. 边界处理
  if (nums.length == 0) return 0
  if (nums.length == 1) return nums[0]

  // 2. 不关注排序，只关注最大值
  const maxVal = Math.max(...nums)
  // 3. 初始化总数数组，避免数组越界
  let count = new Array(maxVal + 1).fill(0)
  // 4. 遍历数组，获取 总数-下标 关联数组
  for (let num of nums) {
    count[num] += num
  }

  let prev2 = count[0] // 相当于 dp[i - 2]
  let prev1 = Math.max(count[0], count[1]) // 相当于 dp[i - 1]

  for (let i = 2; i <= maxVal; i++) {
    const curr = Math.max(prev1, prev2 + count[i])
    prev2 = prev1
    prev1 = curr
  }

  return prev1
}

dp[i][j] = dp[i-1][j] + dp[i][j-1] 从上面来一步：dp[i-1][j]

function uniquePaths(m, n):
    创建二维数组 dp，大小为 m x n，所有元素初始为 1

    for i 从 1 到 m-1:
        for j 从 1 到 n-1:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    返回 dp[m-1][n-1]

const dp = Array.from({ length: m }, () => Array(n).fill(1))

🔍 它做的事情就是：

- { length: m }：只是告诉 Array.from 要生成 m 个元素
- () => Array(n).fill(1)：告诉它每一项该填啥 —— 就是一个 n 长度、值全是 1 的数组

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  let dp = Array.from({ length: m }, () => Array(n).fill(1))
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      // 计算到 (i,j) 的路径，限制只能向右向下
      // 所以可以从 dp[i-1][j]，dp[i][j-1] 两个点过来
    }
  }

  return dp[m - 1][n - 1]
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // 窗口长度为 k，一旦窗口长度超过 k，就需要收缩左区间
  // 每次移动右区间，判断区间是否合法，如果合法，更新最大值
  /**
    理解题目逻辑：窗口长度为 k，获取该窗口下最大的值，窗口收缩会出现多个可能的子集，在子集中找到最大的值
 
    1. 遍历数组 nums，循环执行条件是 r < nums.length
    2. 每次移动右侧指针时，将 nums[r] 与存储最值得队列尾巴对比，如果队列的尾部元素小于 nums[r]，一直将队列尾部出队直到尾部元素大于 nums[r]
    3. 一旦 r - l + 1 > k即窗口长度超过k，需要收缩 l（l++），收缩之前判断 num[l] 是否和队列头部元素相等，如果相等，出队队列头部元素

    PS: 出队头部元素不关注 nums[l] 在队列中部或者尾部的情况，因为有新的 nums[r] 大于队列除了队头以外的任意一个值，队列内的元素都有可能被出队
    或者简单记忆（只关注最大值）
 
    4. 移动右指针之前将队头的值存储待定结果集
    5. 返回结果集中的最大值

    错误点：
    1. 将不符合的窗口区间也记录下来了（一定确保 [l,r] 窗口要合格结果才有效）
    2. 区间合格条件需要注意 k 是长度，r 是序列（从0开始），所以区间合格条件是 r >= k - 1

     */
  let l = 0
  let r = 0
  let deque = []
  let res = []
  while (r < nums.length) {
    while (deque.length && nums[r] > deque[deque.length - 1]) {
      deque.pop()
    }
    deque.push(nums[r])
    while (r - l + 1 > k) {
      // 收缩之前判断即将被排除的左端元素是否在单调递减队列头部，若存在，移除该元素
      if (nums[l] == deque[0]) {
        deque.shift()
      }
      // 收缩左侧指针
      l++
    }
    if (r >= k - 1) {
      // 区间合格的时候，队列最大值才有意义
      res.push(deque[0] || 0)
    }
    r++
  }

  return res
}

nums = [8, 2, 4, 7]
limit = 4

/**
 * @param {number[]} nums
 * @param {number} limit
 * @return {number}
 */
var longestSubarray = function (nums, limit) {
  /**
    整理题目：
    数组 nums，连续元素间的绝对值 <= limit，要求返回符合的窗口长度（max）
    👉 绝对值考虑区间的最大最小值
    👉 两个队列来分别记录区间拥有的最大、最小值
    👉 没有长度限制，因此更新绝对值没有限定条件，每次移动右指针都需要更新
    关注：何时收缩左指针 👉 一旦绝对值 > limit 就需要收缩左指针
    收缩左指针注意事项：
    判断左指针对应元素是否在两个队列的队头，如果在，将队列头部出队（单调队列只关注队头，nums[l] 出现在队中或者队尾，一旦有新的更符合条件的元素入队，随时会被出队，因此不关注）

    1. 遍历整个 nums，循环结束条件是 r < nums.length
    2. 判断极值队列中不为空，将队列尾部大于/小于 nums[r] 的元素移除出队
    2. 分别将 nums[r] 压入队列
    3. while 循环设置收缩左指针的逻辑 Math.abs(max-min) > k 时，收缩左指针 l+【收缩之前查看即将被排除的 nums[l] 是否在极值队列的队头影响结果，如果在，将队列队头元素出队】 
    */
  let l = 0
  let r = 0
  let queueMax = []
  let queueMin = []

  let res = 0
  while (r < nums.length) {
    while (queueMax.length && nums[r] > queueMax[queueMax.length - 1]) {
      queueMax.pop()
    }
    queueMax.push(nums[r])

    while (queueMin.length && nums[r] < queueMin[queueMin.length - 1]) {
      queueMin.pop()
    }

    queueMin.push(nums[r])

    // l 收缩逻辑
    if (queueMax.length && queueMin.length && Math.abs(queueMax[0] - queueMin[0]) > limit) {
      // 收缩之前检查(检查一次就行，不需要用 while)
      if (queueMax[0] == nums[l]) {
        queueMax.shift()
      }
      if (queueMin[0] == nums[l]) {
        queueMin.shift()
      }

      // 收缩区间
      l++
    }

    res = Math.max(r - l + 1, res)
    r++
  }
  console.log({ res })
  return res
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  // 翻转 k 个 0 得到最长连续 1 的长度
  // 把最长连续1看作窗口，内部只能包含 <= k 个，否则窗口不合法（>k)，就需要收缩左区间
  // 直到内部0的个数 < k之前，都一直收缩左区间
  // 每次移动右指针都记录当前连续 1 的长度

  let l = 0
  let count = 0
  let len = 0
  for (let r = 0; r < nums.length; r++) {
    if (nums[r] == 0) {
      // 右指针遍历的时候遇到 0 就更新当前窗口中 0 的个数
      count++
    }
    while (count > k) {
      // 窗口中 0 的个数超过题目限制的 k ，收缩左区间确保窗口是合法的
      if (nums[l] == 0) count--
      // 右移左指针
      l++
    }
    // 每次移动右指针的时候，记录当前窗口的长度
    len = Math.max(r - l + 1, len)
  }
  return len
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  // 翻转 k 个 0 得到最长连续 1 的长度
  // 把最长连续1看作窗口，内部只能包含 <= k 个，否则窗口不合法（>k)，就需要收缩左区间
  // 直到内部0的个数 < k之前，都一直收缩左区间
  // 每次移动右指针都记录当前连续 1 的长度

  let l = 0
  let r = 0
  let count = 0
  let len = 0
  while (r < nums.length) {
    // 遇到 0 更新 count
    if (nums[r] == 0) count++
    // 一旦 count > k 收缩左指针
    while (count > k) {
      // 收缩之前判断，即将被排除的元素是否为0，是则更新 count
      if (nums[l] == 0) count--
      l++
    }
    // 移动右指针之前记录当前区间的长度
    len = Math.max(len, r - l + 1)
    // 扩张右区间
    r++
  }
  console.log({ len })
  return len
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // 直接检查空数组
  const n = nums.length
  if (n === 0) return [-1, -1]

  function getFirst(nums, target, n) {
    // [l, r]
    let l = 0
    let r = n - 1
    let first = -1
    while (l <= r) {
      const mid = (l + r) >>> 1
      // 找到 target 位置后更新 first 位置，收缩右边界，继续向mid左边寻找是否有更左值
      if (target === nums[mid]) {
        first = mid
        r = mid - 1
      } else if (target > nums[mid]) {
        l = mid + 1
      } else {
        r = mid - 1
      }
    }
    return first
  }

  function getLast(nums, target, n) {
    // [l, r]
    let l = 0
    let r = n - 1
    let last = -1
    while (l <= r) {
      const mid = (l + r) >>> 1
      // 找到 target 位置后更新 last 位置，收缩左边界，继续向mid右边寻找是否有更右值
      if (target === nums[mid]) {
        last = mid
        l = mid + 1
      } else if (target > nums[mid]) {
        l = mid + 1
      } else {
        r = mid - 1
      }
    }
    return last
  }
  let first = getFirst(nums, target, n)
  // 如果找不到第一个位置，说明数组中没有这个元素，那么最后一个位置也是找不到的
  // 循环条件上理解则是 一旦 left 为 -1了，在循环条件 left <= right这个上， right也只能是 -1 了
  if (first === -1) return [-1, -1]
  // 一旦能够找到第一个位置，那么 last 最小也只能是 first
  // 循环条件上理解则是 一旦 left > 0 了，在循环条件 left <= right这个上， right也只能是 > 0 了
  let last = getLast(nums, target, n)
  return [first, last]
}

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

* 1 <= target <= 109
* 1 <= nums.length <= 105
* 1 <= nums[i] <= 105

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
function minWindow(s, t) {
  let left = 0
  let right = 0
  let required = t.length
  let minL = Infinity
  let minStart = 0
  const ht = {}
  for (let ct of t) {
    ht[ct] = (ht[ct] || 0) + 1
  }

  let n = s.length
  while (right < n) {
    // right 指针走完 s 的长度为止
    let retR = s[right]
    if (ht[retR] > 0) {
      // 如果是t中元素的话，值为数值，而不是 undefined
      required--
    }
    ht[retR]-- // 无论是否为 t 中元素，直接自减去哈希值 undefined - 1 = NaN
    right++

    while (required === 0) {
      // 判断区间长度是否小于 minL，如果小于则更新 minL、minStart
      if (right - left < minL) {
        minL = right - left
        minStart = left
      }
      // 右移左指针，每次移动都直接增加哈希表中该元素值（undefined + 1 = NaN 不影响算法）
      let retL = s[left]
      ht[retL]++
      // 若是该哈希值大于零，则 left 所指的元素是 t 中值
      if (ht[retL] > 0) required++
      left++
    }
  }
  return minL === Infinity ? '' : s.substring(minStart, minStart + minL)
}