算法 - 滑动窗口最大值

Posted on 2026-04-18

1. 题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 k 个数字，滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值组成的数组。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]

窗口位置                    最大值
---------------           -----
[1  3  -1] -3  5  3  6  7    3
 1 [3  -1  -3] 5  3  6  7    3
 1  3 [-1  -3  5] 3  6  7    5
 1  3  -1 [-3  5  3] 6  7    5
 1  3  -1  -3 [5  3  6] 7    6
 1  3  -1  -3  5 [3  6  7]   7

2. 解题思路

2.1 暴力法

每个窗口遍历求最大，O(n·k)，k 大时超时，仅作对比。

2.2 单调递减双端队列（最优）

维护一个存下标的双端队列，保证队列对应元素值从队头到队尾单调递减，队头始终是当前窗口最大值的下标。

对每个新元素 i：

淘汰过期：若队头下标已滑出窗口（queue[0] <= i - k），从队头弹出。
维护单调性：从队尾开始，凡是值 <= nums[i] 的下标全部弹出——它们被 nums[i]「又新又大」地压制，永远不可能再成为答案。
把 i 入队尾。
当 i >= k - 1 开始收集答案，队头即当前窗口最大值。

时间复杂度：O(n)，每个元素最多入队出队各一次；空间复杂度：O(k)。

3. TypeScript 实现

function maxSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    const deque: number[] = []; // 存下标，对应值单调递减
    const res: number[] = [];

    for (let i = 0; i < n; i++) {
        // 1. 队头过期（滑出窗口）
        if (deque.length && deque[0] <= i - k) deque.shift();

        // 2. 队尾所有 <= 当前值的元素失去意义，弹出
        while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        // 3. 当前下标入队
        deque.push(i);

        // 4. 窗口形成后收集队头最大值
        if (i >= k - 1) res.push(nums[deque[0]]);
    }

    return res;
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3,3,5,5,6,7]

说明：JS 数组的 shift() 是 O(n)，严格最坏复杂度会退化；面试可指出用「头指针 index」模拟队列头、或双向链表实现真正 O(1) 出队。此处为清晰用 shift。

4. 面试延伸

单调栈 vs 单调队列：单调栈解决「下一个更大元素」等；单调队列额外处理「窗口左边界过期」，本题是其模板题。
变形：窗口最小值（改成单调递增队列）、绝对值不超过 limit 的最长子数组等，都基于单调队列。
追问：为什么队列存下标而不是值？因为需要靠下标判断队头是否滑出窗口。
另一路线：分块 / 稀疏表(ST) 预处理区间最大值，也能做到接近 O(n)，可作为思路拓展。

难度：困难 | LeetCode 239 | 单调队列模板

算法 - 字符串相加（大数相加）

Posted on 2026-03-14

1. 题目

给定两个用字符串表示的非负整数 num1 和 num2，计算它们之和，并用字符串形式返回。

要求：不能直接使用任何内置的大整数库，也不能把整个输入字符串直接转换成整数（会溢出）。

示例:

输入: num1 = "11", num2 = "123"
输出: "134"

输入: num1 = "999", num2 = "1"
输出: "1000"

2. 解题思路

模拟小学竖式加法，从**个位（字符串末尾）**开始逐位相加并处理进位。

2.1 双指针从尾部向前

i、j 分别指向 num1、num2 的末尾，carry 为进位。
每一步：取当前位数字（指针越界则视为 0），sum = d1 + d2 + carry。
当前结果位 = sum % 10，新的 carry = Math.floor(sum / 10)。
结果字符往前拼接（或 push 后反转）。
循环条件：i >= 0 || j >= 0 || carry——最后的 carry 不能漏。
时间复杂度：O(max(m, n))，空间复杂度：O(max(m, n))（结果串）。

3. TypeScript 实现

3.1 标准双指针

function addStrings(num1: string, num2: string): string {
    let i = num1.length - 1;
    let j = num2.length - 1;
    let carry = 0;
    const res: string[] = [];

    while (i >= 0 || j >= 0 || carry > 0) {
        const d1 = i >= 0 ? num1.charCodeAt(i) - 48 : 0; // '0'.charCodeAt = 48
        const d2 = j >= 0 ? num2.charCodeAt(j) - 48 : 0;
        const sum = d1 + d2 + carry;

        res.push(String(sum % 10));
        carry = Math.floor(sum / 10);

        i--;
        j--;
    }

    return res.reverse().join("");
}

console.log(addStrings("999", "1")); // "1000"

3.2 变体：字符串相乘（大数乘法）

同族题，用 i + j、i + j + 1 定位乘积位在结果数组中的落点，双循环累加后再统一处理进位。面试常作为追问。

4. 面试延伸

为何用 charCodeAt 而非 parseInt：逐字符 + '0' 或 charCodeAt - 48 更快，且体现「不整体转 int」的约束。
JS 的坑：Number 只有 53 位安全整数（Number.MAX_SAFE_INTEGER），超大数相加若直接 + 会丢精度——这正是本题要求模拟竖式的现实动机；实际项目大数运算常用 BigInt。
相关：链表版本「两数相加」(LeetCode 2)，用链表节点从低位到高位模拟同样的进位逻辑。
结果拼接用数组 push + 反转，避免字符串反复 += 头部的 O(n²) 开销。

难度：简单 | LeetCode 415 | 字符串/模拟

算法 - 缺失的第一个正数

Posted on 2026-02-07

1. 题目

给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。

要求：时间复杂度 O(n)，并且只使用常数级别额外空间。

示例:

输入: nums = [3,4,-1,1]
输出: 2
解释: 缺失的最小正整数是 2。

输入: nums = [7,8,9,11,12]
输出: 1

2. 解题思路

关键结论：长度为 n 的数组，答案一定落在 [1, n + 1] 区间内（最理想情况数组恰好是 1..n，则答案为 n+1）。

2.1 原地哈希（把 i 放到位置 i-1）

目标：让数组「归位」——值 x（1 ≤ x ≤ n）应放到下标 x - 1。

遍历数组，对每个 nums[i]，只要它在 [1, n] 且「它该去的位置上的值还不等于它」，就交换过去（循环，因为换回来的值可能也需归位）。
归位后再扫一遍，第一个 nums[i] !== i + 1 的位置，i + 1 就是缺失的最小正数。
时间复杂度：O(n)（每个元素最多被交换归位一次），空间复杂度：O(1)。

2.2 为什么不能用哈希集合？

可以用 Set 存所有正数再从 1 开始找，满足 O(n) 时间，但空间 O(n)，不满足「常数空间」的进阶要求——面试先讲 Set 思路，再优化到原地哈希。

3. TypeScript 实现

3.1 原地哈希（交换法）

function firstMissingPositive(nums: number[]): number {
    const n = nums.length;

    for (let i = 0; i < n; i++) {
        // 只要 nums[i] 在 [1,n] 且没归位，就把它换到 nums[i]-1 处
        while (
            nums[i] > 0 &&
            nums[i] <= n &&
            nums[nums[i] - 1] !== nums[i]
        ) {
            const target = nums[i] - 1;
            [nums[i], nums[target]] = [nums[target], nums[i]];
        }
    }

    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }

    return n + 1; // 1..n 全在，答案为 n+1
}

console.log(firstMissingPositive([3, 4, -1, 1])); // 2

坑点：解构交换 [nums[i], nums[target]] = [...] 中 target 必须先算好；若写成 nums[nums[i]-1] 内联，赋值左侧求值顺序会导致索引错乱。

3.2 标记法（取负，等价思路）

先把所有 ≤0 的数替换成 n+1（移出有效区），再对每个值的绝对值 v（1≤v≤n）把 nums[v-1] 取负作为「出现过」标记，最后第一个非负下标 +1 即答案。同样 O(n) 时间 O(1) 空间。

4. 面试延伸

原地哈希 vs 排序：排序 O(n log n)，原地哈希利用「答案范围有界」把空间压到 O(1)，是本题精髓。
变形题「数组中重复的数字 / 找丢失的数字」都能复用「下标当哈希表」这一模式。
追问：为什么 while 而不是 if？因为一次交换换来的新值可能也需要归位，必须持续下沉。

难度：困难 | LeetCode 41 | 原地哈希经典

算法 - 汉明距离

Posted on 2026-01-09

1. 题目

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例:

输入: x = 1, y = 4
输出: 2
解释:
1   (0 0 0 1)
4   (0 1 0 0)
      ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

2. 解题思路

2.1 异或 + 统计 1 的个数

对应位不同 ⟺ 异或后该位为 1。所以：

n = x ^ y
统计 n 的二进制中 1 的个数（population count）。

统计 1 的个数有两种经典写法：

逐位 n & 1 后右移。
n & (n - 1) 每次抹掉最低位的 1，循环次数 = 1 的个数，更优。
时间复杂度：O(1)（最多 32 位），空间复杂度：O(1)。

注意：JS 的位运算按 32 位有符号整数处理，本题 LeetCode 数据范围 0 ≤ x, y ≤ 2³¹-1，用 ^、& 安全；若涉及无符号右移请用 >>>。

3. TypeScript 实现

3.1 Brian Kernighan 算法（推荐）

function hammingDistance(x: number, y: number): number {
    let n = x ^ y;
    let count = 0;
    while (n) {
        n = n & (n - 1); // 抹掉最低位的 1
        count++;
    }
    return count;
}

console.log(hammingDistance(1, 4)); // 2

3.2 内置位计数（一行流）

1
2
3

const hammingDistanceBitCount = (x: number, y: number): number =>
    (x ^ y).toString(2).split("0").join("").length;
// 或 (x ^ y).toString(2).match(/1/g)?.length ?? 0

4. 面试延伸

4.1 总汉明距离（LeetCode 477）

给数组 nums，求所有数对汉明距离之和。逐位暴力 O(n²·32) 会超时，按位统计更优：

对第 i 位，统计数组中该位为 1 的个数 ones，为 0 的个数 zeros = n - ones，则该位对总距离的贡献为 ones * zeros（每一位独立）。

function totalHammingDistance(nums: number[]): number {
    let total = 0;
    const n = nums.length;

    for (let i = 0; i < 32; i++) {
        let ones = 0;
        for (const x of nums) {
            ones += (x >>> i) & 1;
        }
        total += ones * (n - ones); // 该位 1 与 0 的两两配对数
    }

    return total;
}

时间复杂度：O(32·n)，空间复杂度：O(1)。

4.2 知识点

n & (n-1) 技巧：可用于判断 2 的幂、统计位 1 个数、求两数异或差异。
汉明距离是「信息/编码」基础概念，延伸可谈海明码纠错。

难度：简单 | LeetCode 461 / 477 | 位运算

算法 - 二叉树的锯齿形层序遍历

Posted on 2025-12-05

1. 题目

给你二叉树的根节点 root，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例:

输入: root = [3,9,20,null,null,15,7]
        3
       / \
      9  20
     /  \
    15   7
输出: [[3],[20,9],[15,7]]
解释: 第 0 层从左到右 [3]，第 1 层从右到左 [20,9]，第 2 层从左到右 [15,7]。

2. 解题思路

本质还是层序遍历（BFS），只是在收集结果时按层的奇偶决定正序还是逆序。

2.1 BFS + 奇偶翻转（推荐）

用队列逐层遍历，逻辑与普通层序遍历完全一致。
维护 leftToRight 布尔标记，每处理完一层取反。
该层节点值先按正常顺序存入 level，若当前层应从右到左，则 level.reverse() 后再 push 进结果。
时间复杂度：O(n)，空间复杂度：O(n)。

2.2 双端队列 / 头尾插入

把每层结果用 unshift/push 分别从头或尾插入，避免整层 reverse。写法更巧但可读性略差。

3. TypeScript 实现

3.1 BFS + 层反转

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val = 0) {
        this.val = val;
        this.left = this.right = null;
    }
}

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    if (!root) return [];
    const res: number[][] = [];
    const queue: TreeNode[] = [root];
    let leftToRight = true;

    while (queue.length) {
        const size = queue.length;
        const level: number[] = [];

        for (let i = 0; i < size; i++) {
            const node = queue.shift()!;
            level.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        res.push(leftToRight ? level : level.reverse());
        leftToRight = !leftToRight; // 下一层方向翻转
    }

    return res;
}

3.2 头尾插入（免 reverse）

function zigzagLevelOrderDeque(root: TreeNode | null): number[][] {
    if (!root) return [];
    const res: number[][] = [];
    let queue: TreeNode[] = [root];
    let leftToRight = true;

    while (queue.length) {
        const level: number[] = [];
        const next: TreeNode[] = [];

        for (const node of queue) {
            leftToRight ? level.push(node.val) : level.unshift(node.val);
            if (node.left) next.push(node.left);
            if (node.right) next.push(node.right);
        }

        res.push(level);
        queue = next;
        leftToRight = !leftToRight;
    }

    return res;
}

4. 面试延伸

与二叉树层序遍历、右视图是同一套 BFS 模板的小变形，考察「层」的边界控制（size 快照）。
DFS 也能做：把每层值按奇偶 push/unshift 到 res[depth]，注意方向由 depth % 2 决定。
坑点：level.reverse() 是原地反转，此处无副作用；但在其他共享引用场景要警惕。

难度：中等 | LeetCode 103 | BFS 层序变形

算法 - 二叉树的右视图

Posted on 2025-11-08

1. 题目

给定一棵二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
        1            <---
      /   \
     2     3         <---
      \     \
       5     4       <---
输出: [1,3,4]
解释: 每一层最右边的节点构成右视图。

2. 解题思路

「右视图」本质是求每一层的最右一个节点。两种主流做法：

2.1 BFS 层序遍历（最直观）

用队列逐层遍历，记录每层的节点个数 levelSize，取该层最后一个出队的节点值加入结果。

时间复杂度：O(n)，空间复杂度：O(n)（队列最宽一层的节点数）。

2.2 DFS（根 → 右 → 左）

关键是先遍历右子树。对每一层，第一个被访问到的节点就是右视图节点。用 depth 记录层数，当 res.length === depth 时说明这一层还没收集过节点，push 当前值。

因为先走右，所以「第一个到达」的必然是该层最右侧节点。

3. TypeScript 实现

树节点定义：

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val = 0) {
        this.val = val;
        this.left = this.right = null;
    }
}

3.1 BFS

function rightSideView(root: TreeNode | null): number[] {
    if (!root) return [];
    const res: number[] = [];
    const queue: TreeNode[] = [root];

    while (queue.length) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift()!;
            if (i === size - 1) res.push(node.val); // 本层最后一个
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

    return res;
}

3.2 DFS（先右后左）

function rightSideViewDFS(root: TreeNode | null): number[] {
    const res: number[] = [];

    const dfs = (node: TreeNode | null, depth: number) => {
        if (!node) return;
        // 该层尚未收集，则当前(最右优先)节点即右视图节点
        if (depth === res.length) res.push(node.val);
        dfs(node.right, depth + 1); // 先右
        dfs(node.left, depth + 1);  // 后左
    };

    dfs(root, 0);
    return res;
}

4. 面试延伸

左视图：BFS 取每层 i === 0；DFS 改成「先左后右」。
俯视图 / 剖面等变形考察的是对遍历顺序与层/列归属的理解。
追问：DSF 解法空间上省去队列，但递归栈最坏 O(h)，h 为树高； skewed tree 下退化为 O(n)。
queue.shift() 在 JS 中是 O(n)，严格优化可用双指针索引或自定义队列，面试点出即可。

难度：中等 | LeetCode 199 | BFS/DFS 层序思想

算法 - 全排列（Permutations）

Posted on 2025-10-11

1. 题目

给定一个没有重复数字的数组 nums，返回其所有可能的全排列。可以按任意顺序返回答案。

示例:

1 2	输入: nums = [1,2,3] 输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

2. 解题思路

排列与组合/子集的最大区别：顺序有关，每层都要从头开始选。

2.1 回溯 + used 标记

每一层递归都遍历整个数组，用 used[i] 记录 nums[i] 是否已在当前路径中。
选中一个数就 path.push + used[i] = true，递归进入下一层；返回后撤销（pop + used[i] = false）。
当 path.length === nums.length 时到达叶子节点，收集一个完整排列。

排列数 n!，故：

时间复杂度：O(n·n!)，空间复杂度：O(n)。

2.2 交换法（原地生成，省空间）

在 index 位置，依次把后面的元素换到前面，递归处理 index+1。优点是不需要额外 used 数组，但顺序不保证字典序。

3. TypeScript 实现

3.1 回溯 + used

function permute(nums: number[]): number[][] {
    const res: number[][] = [];
    const path: number[] = [];
    const used = new Array<boolean>(nums.length).fill(false);

    const backtrack = () => {
        if (path.length === nums.length) {
            res.push([...path]);   // 到达叶子才收集
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 同一条路径不能重复用同一个元素
            used[i] = true;
            path.push(nums[i]);

            backtrack();

            path.pop();
            used[i] = false;       // 撤销选择
        }
    };

    backtrack();
    return res;
}

console.log(permute([1, 2, 3]));

3.2 交换法（原地）

function permuteSwap(nums: number[]): number[][] {
    const res: number[][] = [];

    const dfs = (first: number) => {
        if (first === nums.length) {
            res.push([...nums]);
            return;
        }
        for (let i = first; i < nums.length; i++) {
            [nums[first], nums[i]] = [nums[i], nums[first]];
            dfs(first + 1);
            [nums[first], nums[i]] = [nums[i], nums[first]]; // 回溯
        }
    };

    dfs(0);
    return res;
}

4. 面试延伸

变体：Permutations II（含重复数字）：先排序，同层去重 if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue;——前一个相同值未被使用时跳过，保证相同元素只按固定相对顺序出现一次。
子集 vs 组合 vs 排列 的递归起点：子集/组合用 start（不回头），排列每层从 0 开始（靠 used 去重）。这是最容易混的考点。
JS 中 path.push(...) 传引用会污染结果，务必 [...path] 或 path.slice() 拷贝。

难度：中等 | LeetCode 46 | 回溯法核心题

算法 - 子集（Subsets）

Posted on 2025-09-06

1. 题目

给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集，你可以按任意顺序返回解集。

示例:

1 2	输入: nums = [1,2,3] 输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

2. 解题思路

子集总数为 2ⁿ，所以任何解法时间复杂度下限就是 O(n·2ⁿ)。常见三种套路：

2.1 回溯法（选 / 不选）

把问题看成遍历一棵决策树：对每个元素做「选它」或「跳过它」的决定。为了避免产生重复子集，引入 start 参数——每层只允许从当前下标往后选，保证结果按下标递增顺序排列。

递归到任意节点时，path 都是一个合法子集（不只是叶子节点），所以进入递归就收集。
时间复杂度：O(n·2ⁿ)，空间复杂度：O(n)（递归栈）。

2.2 迭代法（逐步扩张）

从 [[]] 开始，每遇到一个新数 x，就把已有所有子集各追加一个 x 形成新子集，并入结果。

2.3 二进制枚举

用 0~2ⁿ-1 的每个整数的二进制位表示「第 i 个元素选或不选」，适合炫技。

3. TypeScript 实现

3.1 回溯法

function subsets(nums: number[]): number[][] {
    const res: number[][] = [];
    const path: number[] = [];

    const backtrack = (start: number) => {
        // 每个节点都是一个合法子集
        res.push([...path]);

        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);       // 选
            backtrack(i + 1);         // 只往后看，避免重复
            path.pop();               // 不选（撤销选择）
        }
    };

    backtrack(0);
    return res;
}

console.log(subsets([1, 2, 3]));
// [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

3.2 迭代法

function subsetsIterative(nums: number[]): number[][] {
    let res: number[][] = [[]];

    for (const x of nums) {
        // 基于「本轮开始前」的子集扩张，不能边遍历边 push 同一数组
        res = [...res, ...res.map((set) => [...set, x])];
    }

    return res;
}

3.3 二进制枚举

function subsetsBitmask(nums: number[]): number[][] {
    const n = nums.length;
    const res: number[][] = [];

    for (let mask = 0; mask < 1 << n; mask++) {
        const subset: number[] = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) subset.push(nums[i]);
        }
        res.push(subset);
    }

    return res;
}

4. 面试延伸

变体：Subsets II（含重复元素）：先排序，同一层中跳过与前一个相同的值 if (i > start && nums[i] === nums[i-1]) continue;。
回溯三板斧：路径（path）→ 选择列表（start 之后的元素）→ 结束条件（遍历完当前层）。收集时机是本题关键：子集问题在每个节点收集，组合问题通常在叶子收集。
与全排列对比：排列每层从 0 开始并用 used 数组去重，子集/组合用 start 剪枝。

难度：简单 | LeetCode 78 | 回溯入门必考

算法 - 盛最多水的容器

Posted on 2025-08-03

1. 题目

给定一个长度为 n 的整数数组 height，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水，返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 选择第 2 条线(height=8)和第 9 条线(height=7)，
     宽度 = 9 - 2 = 7，高度取较短板 min(8,7) = 7，面积 = 7 * 7 = 49。

2. 解题思路

2.1 暴力法（不可取）

枚举所有左右边界对 (i, j)，计算 (j - i) * min(height[i], height[j])，时间复杂度 O(n²)，面试中只作为铺垫。

2.2 对撞双指针（最优）

从最宽区间开始，左右指针 l = 0、r = n - 1，每步计算当前面积并更新最大值，然后移动较短的那一边：

容器高度由短板决定。若 height[l] < height[r]，则所有以 l 为左边、右边界在 (l, r) 之间的方案，宽度更小且高度不会超过 height[l]，必然不如当前解——所以可以直接排除 l，令 l++。
反过来移动长板则可能错过更优解，这是正确性的关键。
相等时移动任意一边均可。

每一步排除一个不可能的边界，n-1 步内完成。

时间复杂度：O(n)
空间复杂度：O(1)

3. TypeScript 实现

function maxArea(height: number[]): number {
    let l = 0;
    let r = height.length - 1;
    let best = 0;

    while (l < r) {
        const h = Math.min(height[l], height[r]);
        best = Math.max(best, h * (r - l));

        // 移动较短的一边，才可能找到更大的面积
        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }

    return best;
}

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

4. 面试延伸

为什么移动短板？ 反证法：移动长板后宽度必减小，而高度受短板限制不会增大，面积只可能变小；移动短板则高度有可能提升，值得一试。
双指针家族对照：两数之和 II、三数之和、接雨水都用到了对撞指针思想。
常见追问：如果要求输出是哪两条线，只需在更新 best 时记录 l、r 即可。

难度：中等 | LeetCode 11 | 对撞双指针经典题

算法 - 函数柯里化 (Currying)

Posted on 2025-07-24

1. 题目

实现一个通用柯里化函数 curry(fn)，把一个「需要 n 个参数」的函数，转换成可以一次传一部分参数、持续返回自身、直到收集够 n 个参数后才真正调用原函数的函数。

示例:

const add = (a, b, c) => a + b + c;
const curried = curry(add);

curried(1)(2)(3);      // 6
curried(1, 2)(3);      // 6
curried(1)(2, 3);      // 6

进阶要求：支持占位符 curry._，允许跳过某参数稍后再填：

1
2
3

const _ = curry._;
curried(_, 2)(1)(3);   // 6
curried(1, _, 3)(2);   // 6

2. 解题思路

柯里化的本质是闭包累积参数。

2.1 基础版（按 arity 触发）

用 fn.length 得到原函数所需参数个数 n。
返回一个 acc 函数，每次调用把新参数并入已累积的 args（闭包持有）。
若 args.length >= n，用 fn.apply(this, args) 真正执行；否则返回一个把新参数继续累积的函数（保持链式）。

判断「够了就执行、没够就返回函数」是核心。为了让 curried(1) 后还能 curried(1)(2)，返回的必须是函数——用 function () { return acc(...args.concat(...arguments)); } 包一层。

2.2 占位符版

在累积参数后，做两步清洗：

记录本次调用是否以「尾部实参」结束，用于决定何时可执行。
只有当「非占位符参数数量 >= n」时才执行；执行前把参数按先前逻辑压缩（去掉多余的前导 _），保证位置对应。

这部分逻辑较绕，面试能写基础版 + 口头讲清占位符思路已足够。

时间复杂度：每次调用 O(已收集参数)。

3. TypeScript 实现

3.1 基础版

function curry(fn: Function) {
    return function curried(this: any, ...args: any[]): any {
        if (args.length >= fn.length) {
            return fn.apply(this, args);
        }
        return (...rest: any[]) => curried.apply(this, [...args, ...rest]);
    };
}

const add = (a: number, b: number, c: number) => a + b + c;
const curriedAdd = curry(add);
console.log(curriedAdd(1)(2)(3));   // 6
console.log(curriedAdd(1, 2)(3));   // 6

3.2 支持占位符版

const _ = Symbol("placeholder");

function curryWithPlaceholder(fn: Function): any {
    const judge = (...args: any[]): any =>
        // 非占位符参数足够时执行
        args.length >= fn.length &&
        args.slice(0, fn.length).every((a) => a !== _)
            ? fn(...args.filter((a) => a !== _))
            : (arg: any, ...rest: any[]) => judge(...replace(args, arg), ...rest);

    // 用新传入的 arg 填补 args 中第一个占位符；没有则追加
    function replace(args: any[], arg: any): any[] {
        const idx = args.indexOf(_);
        if (idx !== -1 && arg !== _) {
            const copy = [...args];
            copy[idx] = arg;
            return copy;
        }
        return [...args, arg];
    }

    return judge;
}

const sum3 = (a: number, b: number, c: number) => a + b + c;
const c3 = curryWithPlaceholder(sum3);
console.log(c3(_, 2)(1)(3));   // 6
console.log(c3(1, _, 3)(2));   // 6
console.log(c3(1)(2)(3));      // 6

// 暴露占位符
curryWithPlaceholder._ = _;

4. 面试延伸

柯里化 vs 部分应用（partial）：柯里化把「多元函数」拆成「一连串一元函数」；部分应用是一次固定若干参数。JS 里 bind 天然就是部分应用：fn.bind(null, 1)。
实战价值：参数复用、延迟执行、函数组合（compose/pipe 需要一元函数）、创建更专用的小函数（如把通用的 log(date, level, msg) 柯里化成 errorLog = log(now, 'error')）。
TS 类型级柯里化是炫技加分项：用递归条件类型 Curry<F> 依据 Parameters<F> 推导出重载签名，展示你对类型体操的掌握。
常见追问：为什么判断用 >= 而非 ===？（箭头函数/默认参数会让 fn.length 变小，容错用 >= 更稳）；fn.length 与 arguments.length 的区别是什么。

难度：中等 | 函数式入门必考 | 闭包与参数复用