滑动窗口与双指针进阶

// 运行环境：Node.js 14+
// 保存为 dsa-l10.js，执行：node dsa-l10.js

// 最长无重复字符子串
function lengthOfLongestSubstring(s) {
  const seen = new Set()
  let left = 0, maxLen = 0
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {        // 出现重复，左边界收缩
      seen.delete(s[left++])
    }
    seen.add(s[right])                  // 右边界纳入
    maxLen = Math.max(maxLen, right - left + 1)
  }
  return maxLen
}
console.log(lengthOfLongestSubstring('abcabcbb')) // 3

function minWindow(s, t) {
  const need = new Map()
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1)
  let left = 0, formed = 0, minLen = Infinity, start = 0
  for (let right = 0; right < s.length; right++) {
    const ch = s[right]
    if (need.has(ch)) {
      need.set(ch, need.get(ch) - 1)
      if (need.get(ch) === 0) formed++
    }
    while (formed === need.size) {       // 窗口已覆盖全部 t
      if (right - left + 1 < minLen) { minLen = right - left + 1; start = left }
      const L = s[left++]
      if (need.has(L)) { if (need.get(L) === 0) formed--; need.set(L, need.get(L) + 1) }
    }
  }
  return minLen === Infinity ? '' : s.slice(start, start + minLen)
}
console.log(minWindow('ADOBECODEBANC', 'ABC')) // 'BANC'

function maxSlidingWindow(nums, k) {
  const q = [], res = []
  for (let i = 0; i < nums.length; i++) {
    while (q.length && nums[q[q.length - 1]] <= nums[i]) q.pop() // 维护递减
    q.push(i)
    if (q[0] <= i - k) q.shift()                                 // 移出窗口
    if (i >= k - 1) res.push(nums[q[0]])
  }
  return res
}
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)) // [3,3,5,5,6,7]