滑动窗口

1. 什么是滑动窗口算法？

滑动窗口算法是一种用于处理数组或字符串问题的技术，通过维护一个窗口（通常是子数组或子字符串）来高效解决问题。窗口在数据上滑动，根据问题需求调整大小或位置。

2. 核心思想

• 窗口定义：窗口由起始指针（left）和结束指针（right）表示，通常初始化为数组或字符串的起点。

• 滑动操作：根据条件移动窗口的起始或结束指针，逐步遍历整个数据。

• 条件判断：在每次滑动时，检查窗口内的元素是否满足特定条件，并更新结果。

3. 适用场景

• 子数组/子字符串问题：如最大子数组和、最小覆盖子串等。

• 固定窗口大小问题：如长度为 k 的子数组的最大平均值。

• 动态窗口大小问题：如无重复字符的最长子串。

4. 实践步骤

• 初始化：设置窗口的起始和结束指针。

• 滑动窗口：根据条件移动指针，扩展或收缩窗口。

• 更新结果：在每次滑动后，检查窗口内的元素并更新结果。

• 终止条件：当窗口滑动到数据末尾时，算法结束。

5. JavaScript 示例代码 示例 1：最大子数组和（固定窗口大小）

function maxSubarraySum(nums, k) {
    if (nums.length < k) return null; // 如果数组长度小于窗口大小，返回 null

    let maxSum = 0;
    let windowSum = 0;
    let left = 0;

    // 初始化窗口
    for (let right = 0; right < k; right++) {
        windowSum += nums[right];
    }
    maxSum = windowSum;

    // 滑动窗口
    for (let right = k; right < nums.length; right++) {
        windowSum += nums[right] - nums[left]; // 加上新元素，减去旧元素
        maxSum = Math.max(maxSum, windowSum);
        left++; // 移动左指针
    }

    return maxSum;
}

const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSubarraySum(nums, k)); // 输出: 16

示例 2：无重复字符的最长子串（动态窗口大小）

function lengthOfLongestSubstring(s) {
    const charIndexMap = new Map(); // 存储字符及其最新索引
    let maxLength = 0;
    let left = 0; // 窗口左边界

    for (let right = 0; right < s.length; right++) {
        const currentChar = s[right];

        // 如果字符已存在且在当前窗口内，移动左指针
        if (charIndexMap.has(currentChar) && charIndexMap.get(currentChar) >= left) {
            left = charIndexMap.get(currentChar) + 1;
        }

        // 更新字符的最新索引
        charIndexMap.set(currentChar, right);

        // 更新最大长度
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

const s = "abcabcbb";
console.log(lengthOfLongestSubstring(s)); // 输出: 3

示例 3：最小覆盖子串（动态窗口大小）

function minWindow(s, t) {
    const targetMap = new Map();
    for (const char of t) {
        targetMap.set(char, (targetMap.get(char) || 0) + 1);
    }

    let left = 0;
    let right = 0;
    let required = targetMap.size;
    let formed = 0;
    let minLength = Infinity;
    let result = "";

    const windowMap = new Map();

    while (right < s.length) {
        const char = s[right];
        windowMap.set(char, (windowMap.get(char) || 0) + 1);

        if (targetMap.has(char) {
            if (windowMap.get(char) === targetMap.get(char)) {
                formed++;
            }
        }

        while (left <= right && formed === required) {
            const currentLength = right - left + 1;
            if (currentLength < minLength) {
                minLength = currentLength;
                result = s.slice(left, right + 1);
            }

            const leftChar = s[left];
            windowMap.set(leftChar, windowMap.get(leftChar) - 1);

            if (targetMap.has(leftChar)) {
                if (windowMap.get(leftChar) < targetMap.get(leftChar)) {
                    formed--;
                }
            }

            left++;
        }

        right++;
    }

    return result;
}

const s = "ADOBECODEBANC";
const t = "ABC";
console.log(minWindow(s, t)); // 输出: "BANC"

示例 4：最大子数组和（滑动窗口思想）

问题描述 给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例

输入: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出: 6
解释: 连续子数组 [4, -1, 2, 1] 的和最大，为 6。

实现思路

滑动窗口：

• 维护一个窗口，窗口内的和始终是当前最大的子数组和。

• 如果当前窗口的和变为负数，则舍弃窗口（因为负数会拖累后续的和），重新开始计算。

动态规划思想：

• 遍历数组，计算以当前元素结尾的最大子数组和。

• 如果前一个元素的最大子数组和是负数，则从当前元素重新开始。

JavaScript 实现

function maxSubarraySum(nums) {
    if (nums.length === 0) return 0; // 空数组返回 0

    let maxSum = nums[0]; // 全局最大和
    let currentSum = nums[0]; // 当前窗口的和

    for (let i = 1; i < nums.length; i++) {
        // 如果当前窗口的和是负数，则舍弃窗口，从当前元素重新开始
        if (currentSum < 0) {
            currentSum = nums[i];
        } else {
            // 否则，继续扩展窗口
            currentSum += nums[i];
        }

        // 更新全局最大和
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

// 测试
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubarraySum(nums)); // 输出: 6

代码解析

1. 初始化：

• maxSum 存储全局最大和，初始值为数组的第一个元素。

• currentSum 存储当前窗口的和，初始值为数组的第一个元素。

2. 遍历数组：

• 如果 currentSum 是负数，说明当前窗口的和已经拖累了后续的计算，因此舍弃窗口，从当前元素重新开始。

• 否则，继续扩展窗口，将当前元素加入窗口。

3. 更新全局最大和：

每次遍历后，更新 maxSum 为 maxSum 和 currentSum 中的较大值。

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组。

• 空间复杂度：O(1)，只使用了常数级别的额外空间。

示例运行

const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubarraySum(nums)); // 输出: 6

总结 这个问题是滑动窗口和动态规划的经典结合。

核心思想是：如果当前窗口的和是负数，则舍弃窗口，重新开始。

这种方法高效且易于理解，适合面试和实际应用。

6. 总结 滑动窗口算法通过维护一个窗口来高效解决问题，适用于多种场景。掌握其核心思想和实践步骤，能够有效提升算法能力。JavaScript 的实现方式与其他语言类似，关键在于理解窗口的滑动逻辑和条件判断。

回溯算法

回溯算法是一种通过递归枚举所有可能解的方法。它尝试分步解决问题，如果发现当前步骤不能得到有效的解，就回退到上一步，尝试其他可能的路径。回溯算法通常用于解决组合、排列、子集、棋盘等问题。

1. 回溯算法的核心思想

• 选择：在当前步骤中，尝试所有可能的选择。

• 递归：对于每一个选择，递归地处理下一步。

• 撤销：如果发现当前选择不能得到有效解，回退到上一步，尝试其他选择。

回溯算法可以看作是一种深度优先搜索（DFS），但它会在搜索过程中剪枝，避免无效的搜索路径。

3. 回溯算法的模板

以下是回溯算法的通用模板：

function backtrack(路径, 选择列表) {
    if (满足结束条件) {
        结果.push(路径); // 将当前路径加入结果
        return;
    }

    for (选择 of 选择列表) {
        做选择; // 将当前选择加入路径
        backtrack(路径, 选择列表); // 递归
        撤销选择; // 回退到上一步
    }
}

示例 1：全排列问题

问题描述：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

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

代码实现：

function permute(nums) {
    const result = [];

    function backtrack(path, used) {
        if (path.length === nums.length) {
            result.push([...path]); // 找到一个排列
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 跳过已使用的元素
            path.push(nums[i]); // 做选择
            used[i] = true;
            backtrack(path, used); // 递归
            path.pop(); // 撤销选择
            used[i] = false;
        }
    }

    backtrack([], []); // 初始路径为空，没有元素被使用
    return result;
}

运行过程：

• 从 1 开始，递归处理 [2, 3]，得到 [1, 2, 3] 和 [1, 3, 2]。

• 回退到 1，选择 2，递归处理 [1, 3]，得到 [2, 1, 3] 和 [2, 3, 1]。

• 回退到 2，选择 3，递归处理 [1, 2]，得到 [3, 1, 2] 和 [3, 2, 1]。

示例 2：子集问题 问题描述：给定一个不含重复元素的整数数组 nums，返回其所有可能的子集（幂集）。

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

代码实现：

function subsets(nums) {
    const result = [];

    function backtrack(start, path) {
        result.push([...path]); // 将当前路径加入结果
        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]); // 做选择
            backtrack(i + 1, path); // 递归
            path.pop(); // 撤销选择
        }
    }

    backtrack(0, []); // 从第 0 个元素开始
    return result;
}

运行过程：

初始路径为空 []。

• 选择 1，递归处理 [2, 3]，得到 [1]、[1, 2]、[1, 2, 3]、[1, 3]。

• 回退到 1，选择 2，递归处理 [3]，得到 [2]、[2, 3]。

• 回退到 2，选择 3，得到 [3]。

示例 3：组合总和问题 问题描述：给定一个无重复元素的数组 candidates 和一个目标数 target，找出所有可以使数字和为目标数的组合。每个数字可以重复使用。

示例： 输入：candidates = [2, 3, 6, 7], target = 7 输出：[[2, 2, 3], [7]]

代码实现：

function combinationSum(candidates, target) {
    const result = [];

    function backtrack(start, path, remaining) {
        if (remaining === 0) {
            result.push([...path]); // 找到一个组合
            return;
        }

        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) continue; // 剪枝
            path.push(candidates[i]); // 做选择
            backtrack(i, path, remaining - candidates[i]); // 递归
            path.pop(); // 撤销选择
        }
    }

    backtrack(0, [], target); // 从第 0 个元素开始
    return result;
}

运行过程：

• 选择 2，递归处理剩余目标 5，得到 [2, 2, 3]。

• 回退到 2，选择 3，递归处理剩余目标 4，无解。

• 回退到 3，选择 6，无解。

• 回退到 6，选择 7，得到 [7]。

4. 总结 回溯算法通过递归枚举所有可能的解，适用于组合、排列、子集等问题。它的核心思想是：

• 做选择：尝试当前步骤的所有可能选择。

• 递归：处理下一步。

• 撤销选择：回退到上一步，尝试其他选择。

通过剪枝和优化，回溯算法可以高效地解决许多复杂问题。

单调栈

单调栈是一种特殊的栈结构，它的特点是栈中的元素始终保持单调性（单调递增或单调递减）。单调栈通常用于解决一些需要快速找到某个元素左边或右边第一个比它大（或小）的元素的问题。

1. 单调栈的核心思想

单调性：栈中的元素按照一定的顺序排列，比如从小到大（单调递增）或从大到小（单调递减）。

单调栈常用于解决以下类型的问题：

• 找到数组中每个元素左边或右边第一个比它大（或小）的元素。

• 计算某个元素作为最小值或最大值时的区间范围。

2. 操作规则：

• 当新元素入栈时，如果破坏了栈的单调性，则弹出栈顶元素，直到满足单调性为止。

• 弹出的元素通常会被用来计算某些结果（比如面积、距离等）。

3. 单调栈的两种类型

• 单调递增栈：

• 栈中的元素从栈底到栈顶是递增的。

• 用于解决“找到左边或右边第一个比当前元素小的元素”的问题。

• 单调递减栈：

  • 栈中的元素从栈底到栈顶是递减的。
  • 用于解决“找到左边或右边第一个比当前元素大的元素”的问题。

4. 单调栈的应用场景

• 柱状图中最大的矩形：使用单调递增栈找到每个柱子左边和右边第一个比它小的柱子，从而计算以当前柱子为高度的最大矩形面积。

• 下一个更大元素：给定一个数组，找到每个元素右边第一个比它大的元素。

• 接雨水问题：使用单调栈计算每个位置可以接到的雨水量。

单调栈的代码模板 以下是单调栈的通用代码模板（以单调递增栈为例）：

function monotonicStack(nums) {
    const stack = []; // 单调栈
    const result = []; // 存储结果

    for (let i = 0; i < nums.length; i++) {
        // 当栈不为空且当前元素小于栈顶元素时，弹出栈顶元素
        while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
            const top = stack.pop(); // 弹出栈顶元素
            // 在这里可以根据需要计算某些结果
        }
        stack.push(i); // 将当前元素的下标压入栈
    }

    return result;
}

5. 单调栈的示例 示例 1：下一个更大元素

给定一个数组 nums，找到每个元素右边第一个比它大的元素。

var nextGreaterElement = function(nums) {
    const stack = []; // 单调递减栈
    const result = new Array(nums.length).fill(-1); // 初始化结果数组

    for (let i = 0; i < nums.length; i++) {
        // 当栈不为空且当前元素大于栈顶元素时，更新结果
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            const top = stack.pop(); // 弹出栈顶元素
            result[top] = nums[i]; // 当前元素是栈顶元素的下一个更大元素
        }
        stack.push(i); // 将当前元素的下标压入栈
    }

    return result;
};

输入：

nums = [2, 1, 2, 4, 3];

输出：

[4, 2, 4, -1, -1];

解释：

• 对于元素 2，右边第一个比它大的是 4。

• 对于元素 1，右边第一个比它大的是 2。

• 对于元素 2，右边第一个比它大的是 4。

• 对于元素 4，右边没有比它大的元素，返回 -1。

• 对于元素 3，右边没有比它大的元素，返回 -1。

示例 2：柱状图中最大的矩形

使用单调递增栈找到每个柱子左边和右边第一个比它小的柱子，从而计算最大矩形面积。

var largestRectangleArea = function(heights) {
    heights = [0, ...heights, 0]; // 添加边界
    const stack = []; // 单调递增栈
    let maxArea = 0;

    for (let i = 0; i < heights.length; i++) {
        // 当当前柱子高度小于栈顶柱子高度时，计算栈顶柱子的矩形面积
        while (stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]) {
            const height = heights[stack.pop()]; // 弹出栈顶柱子
            const width = i - stack[stack.length - 1] - 1; // 计算宽度
            maxArea = Math.max(maxArea, height * width); // 更新最大面积
        }
        stack.push(i); // 将当前柱子的下标压入栈
    }

    return maxArea;
};

输入：

heights = [2, 1, 5, 6, 2, 3];

输出：

10

解释：最大矩形的高度为 5，宽度为 2，面积为 10。

6. 单调栈的时间复杂度 每个元素最多被压入和弹出栈一次，时间复杂度为 O(n)其中 n 是数组的长度。

7. 总结 单调栈是一种高效的数据结构，适用于解决一些需要快速找到某个元素左边或右边第一个比它大（或小）的元素的问题。它的核心思想是通过维护栈的单调性，快速排除不符合条件的元素，从而降低时间复杂度。

版权所有

版权归属：tuyongtao1

许可证：署名 4.0 国际 (CC-BY-4.0)