盛最多水的容器

问题描述

给定一个长度为 n 的非负整数数组 height，其中 height[i] 表示第 i 条垂直线的高度。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

注意：你不能倾斜容器。

示例

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水的最大值为 49（即选择第2个和第9个柱子）。

解决思路

方法：双指针法

1. 初始化：使用两个指针，一个在数组的开头（left），一个在数组的末尾（right）
2. 计算当前面积：面积 = min(height[left], height[right]) * (right - left)
3. 移动指针：移动高度较小的指针（因为移动较高的指针不可能得到更大的面积）
4. 更新最大面积：每次计算后比较并保存最大值
5. 终止条件：当 left 和 right 相遇时停止

为什么这个方法有效？

• 贪心选择：每次移动较短的边，保留了可能产生更大面积的机会
• 完备性：通过双指针的移动，我们检查了所有可能的容器组合
• 高效性：只需要一次线性扫描，时间复杂度为 O(n)

JavaScript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function maxArea(height) {
    let max = 0;
    let left = 0;
    let right = height.length - 1;
    
    while (left < right) {
        // 计算当前面积
        const currentArea = Math.min(height[left], height[right]) * (right - left);
        // 更新最大面积
        max = Math.max(max, currentArea);
        // 移动指针
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return max;
}

示例解析

以输入 [1,8,6,2,5,4,8,3,7] 为例：

初始状态：
left=0 (height=1), right=8 (height=7)
面积=min(1,7)*8=8
max=8
移动left（因为height[left]较小）

下一步：
left=1 (height=8), right=8 (height=7)
面积=min(8,7)*7=49
max=49
移动right（因为height[right]较小）

下一步：
left=1 (height=8), right=7 (height=3)
面积=min(8,3)*6=18
max保持49
移动right

...（继续此过程直到left >= right）

复杂度分析

• 时间复杂度：O(n)，只需一次扫描
• 空间复杂度：O(1)，只使用了常数个额外空间

边界情况考虑

1. 空数组或单元素数组：返回0（无法形成容器）
2. 所有高度相同：最大面积为 height[0] * (n-1)
3. 高度为0：0高度不会影响计算（因为面积由较短的边决定）

可视化示例

高度图：
8|       ■       ■
7|       ■       ■   ■
6|   ■   ■       ■   ■
5|   ■   ■   ■   ■   ■
4|   ■   ■   ■   ■   ■
3|   ■   ■   ■   ■   ■   ■
2|   ■   ■   ■   ■   ■   ■
1|■  ■   ■   ■   ■   ■   ■
 0 1 2 3 4 5 6 7 8 9

最大面积容器：
左边界：第2个柱子（height=8）
右边界：第9个柱子（height=7）
宽度：7（9-2）
高度：min(8,7)=7
面积：7*7=49

总结

盛水容器问题的双指针解法：

1. 简单高效，时间复杂度为线性
2. 关键在于理解为什么移动较短的指针是正确的
3. 适用于各种边界情况
4. 是双指针技巧的经典应用场景

两两交换链表中的节点

问题描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

注意：不能只是单纯改变节点内部的值，而是需要实际进行节点交换。

示例

输入：1->2->3->4
输出：2->1->4->3

解决思路

方法：迭代法

1. 使用一个哑节点(dummy node)作为链表的起始点
2. 维护三个指针：
   • prev：指向当前要交换的两个节点的前一个节点
   • first：指向要交换的第一个节点
   • second：指向要交换的第二个节点
3. 每次交换两个节点，并更新指针位置

算法步骤

1. 创建哑节点，指向链表头部
2. 初始化prev指针指向哑节点
3. 当prev.next和prev.next.next都存在时：
   • 设置first和second指针
   • 执行交换操作
   • 移动prev指针到下一组的前面

JavaScript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function swapPairs(head) {
    // 创建哑节点
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    
    while (prev.next !== null && prev.next.next !== null) {
        // 初始化要交换的两个节点
        const first = prev.next;
        const second = prev.next.next;
        
        // 执行交换
        first.next = second.next;
        second.next = first;
        prev.next = second;
        
        // 移动prev指针
        prev = first;
    }
    
    return dummy.next;
}

复杂度分析

• 时间复杂度：O(n)，需要遍历整个链表一次
• 空间复杂度：O(1)，只使用了常数个额外空间

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function swapPairs(head) {
    // 递归终止条件
    if (head === null || head.next === null) {
        return head;
    }
    
    // 要交换的两个节点
    const first = head;
    const second = head.next;
    
    // 递归交换后面的节点
    first.next = swapPairs(second.next);
    second.next = first;
    
    // 返回新的头节点
    return second;
}

边界情况考虑

1. 空链表：直接返回null
2. 单节点链表：直接返回该节点
3. 奇数长度链表：最后一个节点不交换

问题形象化理解

想象你有一串珍珠项链，每颗珍珠上有一个数字。现在要求你把相邻的两颗珍珠交换位置：

原项链：①→②→③→④→⑤
交换后：②→①→④→③→⑤

为什么需要哑节点？

哑节点（dummy node）就像一个”临时挂架”，帮助我们统一处理头节点的交换：

加入哑节点后：
哑→①→②→③→④→⑤

这样我们就不需要特殊处理头节点了，所有节点交换都可以用相同的方式处理。

详细步骤拆解（以 1→2→3→4 为例）

初始状态

哑→①→②→③→④→null
↑
prev

第一次交换（交换①和②）

1. 确定要交换的节点：

   • first = prev.next = ①
   • second = prev.next.next = ②

2. 执行交换：

   • ①.next = ②.next → ①.next = ③
   • ②.next = ①
   • prev.next = ②

3. 交换后状态：

   哑→②→①→③→④→null
   ↑
   prev

第二次交换（交换③和④）

1. 移动prev指针：prev = ①

2. 确定要交换的节点：

   • first = ①.next = ③
   • second = ①.next.next = ④

3. 执行交换：

   • ③.next = ④.next → ③.next = null
   • ④.next = ③
   • ①.next = ④

4. 交换后状态：

   哑→②→①→④→③→null
   ↑
   prev

终止条件

当prev.next或prev.next.next为null时停止（没有足够的节点可以交换了）

指针变化图解

初始：
dummy → ① → ② → ③ → ④ → null
 ↑prev   ↑f   ↑s

第一次交换后：
dummy → ② → ① → ③ → ④ → null
             ↑prev ↑f   ↑s

第二次交换后：
dummy → ② → ① → ④ → ③ → null
                         ↑prev

代码逐行解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function swapPairs(head) {
    const dummy = new ListNode(0); // 创建哑节点
    dummy.next = head;            // 哑节点指向原链表头
    let prev = dummy;             // prev初始指向哑节点
    
    // 当还有至少两个节点可以交换时
    while (prev.next && prev.next.next) {
        const first = prev.next;      // 第一个要交换的节点
        const second = prev.next.next; // 第二个要交换的节点
        
        // 执行交换
        first.next = second.next; // ①指向③
        second.next = first;      // ②指向①
        prev.next = second;       // prev指向②
        
        prev = first; // 移动prev到下一组的前面（现在是①）
    }
    
    return dummy.next; // 返回新链表的头
}

常见误区

1. 忘记更新prev指针：会导致无限循环
2. 交换顺序错误：必须先保存second.next，再改变second.next
3. 边界条件处理：空链表或单节点链表直接返回

生活化类比

想象你在帮小朋友排队：

• 每次让相邻的两个小朋友交换位置
• 你站在前一对小朋友后面（prev指针）
• 指挥前面两个小朋友（first和second）换位置
• 然后你走到刚刚换完的那对小朋友后面
• 重复这个过程直到队尾

递归解法理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function swapPairs(head) {
    // 递归终止条件：没有节点或只有一个节点
    if (!head || !head.next) return head;
    
    // 要交换的两个节点
    const first = head;
    const second = head.next;
    
    // first指向后面已经交换好的链表
    first.next = swapPairs(second.next);
    // second指向first完成交换
    second.next = first;
    
    // 返回新的头节点
    return second;
}

递归过程：

1. 先递归到链表末尾
2. 从后往前两两交换
3. 每次返回交换后的子链表头

复杂度分析

• 时间复杂度：O(n)，每个节点只被访问一次
• 空间复杂度：
  • 迭代法：O(1)
  • 递归法：O(n)（递归调用栈）

总结

两两交换链表节点的关键：

1. 使用哑节点简化头节点处理
2. 维护三个关键指针：prev、first、second
3. 按照固定顺序执行指针修改
4. 每次交换后正确移动prev指针

通过这种逐步交换的方式，我们可以高效地完成链表节点的两两交换。