// 滑動(dòng)窗口算法解題思路
1. 使用雙指針技巧，初始化left=right=0,把索引左閉右開區(qū)間[left, right）稱為一個(gè)窗口
2. 先不斷增加right指針，擴(kuò)大窗口
3. 當(dāng)結(jié)果不符合要求，進(jìn)行窗口收縮
4. 重復(fù)2、3步，直到終止條件

// 該問題是一個(gè)滑動(dòng)窗口問題
// 滑動(dòng)窗口算法解題思路
// 1. 使用雙指針技巧，初始化left=right=0,把索引左閉右開區(qū)間[left, right）稱為一個(gè)窗口
// 2. 先不斷增加right指針，擴(kuò)大窗口
// 3. 當(dāng)結(jié)果不符合要求，進(jìn)行窗口收縮
// 4. 重復(fù)2、3步，直到終止條件
function findContinuousSequence(target) {
    const result = [];
    // 滑動(dòng)窗口
    const window = [];
    let sum = 0;
    const middle = (target + 1) << 1;
    let left = 1;
    let right = 1;

    for (let i = 1; i <= middle; i++) {
        // 擴(kuò)充窗口
        window.push(i);
        sum += i;
        right++;

        // 判斷是否收縮窗口
        while (sum > target) {
            // 進(jìn)行窗口收縮
            const temp = window.shift();
            left++;
            sum -= temp;
        }

        if (sum === target && window.length > 1) {
            result.push([...window]);
        }
    }

    return result;
}

console.log(findContinuousSequence(9));

/**
 * 最長(zhǎng)不含重復(fù)字符的子字符串
 */
// 可以通過滑動(dòng)窗口解決
function lengthOfLongestSubstring(s) {
    // 滑動(dòng)窗口
    const window = {};

    // 左右指針
    let left = 0;
    let right = 0;

    let result = 0;

    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);

        // 擴(kuò)充窗口
        window[c] = window[c] ? window[c] + 1 : 1;
        right++;

        // 判斷是否收縮窗口
        while (window[c] > 1) {
            // 進(jìn)行窗口收縮
            const leftC = s.charAt(left);
            window[leftC]--;
            left++;
        }

        result = Math.max(result, right - left);
    }

    return result;
}

const s = 'abcabcbb';
console.log(lengthOfLongestSubstring(s));

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長(zhǎng)度最小的子數(shù)組。

// 滑動(dòng)窗口
function minSubArrayLen(target, nums) {
    let left = 0;
    let right = 0;
    let sum = 0;
    let result = Infinity;

    while (right < nums.length) {
        // 更新狀態(tài)
        sum += nums[right];
        right++;

        // 收縮窗口
        while (sum >= target) {
            result = Math.min(result, right - left);
            const presentVal = nums[left];
            // 更新狀態(tài)
            sum -= presentVal;
            left++;
        }
    }

    return result === Infinity ? 0 : result;
}

function lengthOfLongestSubstring(s) {
    // 滑動(dòng)窗口
    const window = {};

    // 滑動(dòng)窗口的兩個(gè)指針
    let left = 0;
    let right = 0;

    // 結(jié)果
    let result = 0;

    // 循環(huán)終止條件
    while (right < s.length) {
        const c = s[right];

        // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
        window[c] = window[c] ? window[c] + 1 : 1;

        // 移動(dòng)窗口右側(cè)
        right++;

        // 判斷左側(cè)窗口是否要收縮
        while (window[c] > 1) {
            const d = s[left];

            // 左側(cè)窗口收縮
            left++;

            // 進(jìn)行窗口內(nèi)的一系列更新
            window[d]--;
        }

        // 更新答案
        result = Math.max(result, right - left);
    }

    return result;
}

const s = 'abcabcbb';

console.log(lengthOfLongestSubstring(s));

/**
 * 算法思路：
 * 滑動(dòng)窗口
 * s2包含s1的最小子串，然后最小子串長(zhǎng)度跟s1長(zhǎng)度相等
 */

function checkInclusion(s1, s2) {
    // 需要湊齊的字符
    const need = {};
    for (let i = 0; i < s1.length; i++) {
        need[s1[i]] = need[s1[i]] ? need[s1[i]] + 1 : 1;
    }

    // 滑動(dòng)窗口
    const window = {};

    // 滑動(dòng)窗口的兩端
    let left = 0;
    let right = 0;

    // 表示窗口中滿足need部分的字符數(shù)
    let valid = 0;

    while (right < s2.length) {
        const c = s2[right];

        // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
        if (need[c]) {
            window[c] = window[c] ? window[c] + 1 : 1;
            if (window[c] === need[c]) {
                valid++;
            }
        }

        // 移動(dòng)窗口右側(cè)
        right++;

        // 判斷左側(cè)窗口是否要收縮（當(dāng)s1字符和滑動(dòng)窗口字符大小相等，此時(shí)就要收縮敞口）
        while (right - left >= s1.length) {
            // 在這里判斷是否找到了合法的子串
            if (valid === Object.keys(need).length) {
                return true;
            }

            const d = s2[left];
            left++;

            // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
            if (need[d] !== undefined) {
                if (window[d] === need[d]) {
                    valid--;
                }

                window[d]--;
            }
        }
    }

    return false;
}

const s1 = 'ab';
const s2 = 'eidbaooo';

console.log(checkInclusion(s1, s2));

// 首先建立一個(gè)單調(diào)隊(duì)列的類
class MonotonicQueue {
    constructor() {
        this.queue = [];
    }

    // 在隊(duì)尾添加元素n
    // 該函數(shù)在加入元素時(shí)，會(huì)將其前面比自己小的元素全部刪除掉
    push(n) {
        // 將前面小于自己的元素全部刪除掉
        while (this.queue.length && n > this.queue[this.queue.length - 1]) {
            this.queue.pop();
        }

        this.queue.push(n);
    }

    // 對(duì)頭元素如果是n，則刪除它
    pop(n) {
        if (this.queue.length > 0 && n === this.queue[0]) {
            this.queue.shift();
        }
    }

    // 返回當(dāng)前隊(duì)列中的最大值
    // 因?yàn)閜ush元素時(shí)都會(huì)將比自己小的刪除掉，最終結(jié)果就是一個(gè)遞減的順序，則最大值就是隊(duì)列首部?jī)?nèi)容
    max() {
        return this.queue[0];
    }
}
function maxSlidingWindow(nums, k) {
    // 實(shí)例化一個(gè)單調(diào)隊(duì)列
    const monotonicQueue = new MonotonicQueue();
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        // 先填滿整個(gè)滑動(dòng)窗口的k-1個(gè)元素
        if (i < k - 1) {
            monotonicQueue.push(nums[i]);
        } else {
            // 窗口向前滑動(dòng)，添加新元素
            monotonicQueue.push(nums[i]);
            // 記錄當(dāng)前窗口的最大值
            result.push(monotonicQueue.max());
            // 移除隊(duì)列首部元素
            monotonicQueue.pop(nums[i - k + 1]);
        }
    }

    return result;
}