相向双指针（二）

来源：基础算法精讲 by 灵茶山艾府

视频精讲：相向双指针（二）

题目	代码	备注
11. 盛最多水的容器	代码
42. 接雨水	代码	额外讲了前后缀分解
125. 验证回文串	代码	*课后作业
2105. 给植物浇水 II	代码	*课后作业

例题

盛最多水的容器

• 相向双指针，选两端计算面积
• 木桶效应：每次移动较矮的一边，因为移动高的不可能让面积变大
• 相等时移动哪边都可以（这里选择 r--）

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    //选两端，木桶原理，移动矮的找更大的；
    //相向双指针
    //不知道怎么处理相等的情况
    let l = 0, r = height.length -1;
    let ans = 0, minh = 0;
    while(l < r){
        minh = Math.min(height[l],height[r]);
        ans = Math.max(ans,(r-l)*minh)
        if (height[l] ===  height[r]) r--;
        else if(height[l] > height[r]) r--;
        else l++;
    }
    return ans;
};

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

接雨水 - 前后缀分解

• 每个位置能接的雨水 = min(左边最大值, 右边最大值) - 当前高度
• 预处理两个数组：preMax[i] 前缀最大值，suffMax[i] 后缀最大值
• 最后遍历一次累加每个位置的雨水量

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    // 根据例题发现，每次计算雨水格子，需要左边的最大值，右边的最大值，与当前值，所以需要维护两个数组
    //注意前缀和的生成
    let l = 0, n = height.length;
    let preMax = Array(n)
    let suffMax = Array(n)
    preMax[0] = height[0];
    suffMax[n - 1] = height[n - 1];
    for (let i = 1; i < n; i++) {
        preMax[i] = Math.max(height[i], preMax[i - 1])
    }

    for (let i = n - 2; i >= 0; i--) {
        suffMax[i] = Math.max(height[i], suffMax[i+1])
    }

    let ans = 0;
    for (let i = 0; i < n; i++) {
        ans += Math.min(preMax[i], suffMax[i]) - height[i];
    }

    return ans;
};

时间复杂度：O(n)，空间复杂度：O(n)（两个辅助数组）

接雨水 - 双指针

• 木桶原理的延伸：维护 preMax 和 suffMax，哪边小就处理哪边
• 用指针移动 + 取最大值来动态维护前后最大值，省去辅助数组
• 多画图模拟，多测试

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    //双指针的话，原理也是木桶，找到最小的一方计算那一方的ans
    //不知道怎么维护前后的最大值？还是比较呗，
    //指针+取最大，来维护前后最大值；
    let ans = 0, l = 0, r = height.length - 1, preMax = height[0], suffMax = height[r];

    while (l < r) {
        if (height[l] < height[r]) {
            ans += preMax - height[l++];
            preMax = Math.max(preMax, height[l])
        }
        else {
            ans += suffMax - height[r--];
            suffMax = Math.max(suffMax, height[r])
        }
    }
    return ans;
};

时间复杂度：O(n)，空间复杂度：O(1)（相比前后缀分解优化了空间）

作业题

验证回文串

• 先过滤非字母数字字符，再用双指针从两端向中间比较
• 正则 /[a-zA-Z0-9]/ 判断是否为合法字符
• toLowerCase() 统一大小写后比较

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
    //toLowerCase,
    //正反l,r
    //不能直接剔除？
    const n = s.length;

    let reg = /[a-zA-Z0-9]/;
    let ss = "";
    // 使用正则表达式一次性过滤并转为小写
    // const filtered = s.toLowerCase().replace(/[^a-z0-9]/g, '');
    for (let i = 0; i < n; i++) {
        if (reg.test(s[i])) ss += s[i];
    }
    // 添加空字符串检查
    if (ss.length === 0) return true;
    let l = 0, r = ss.length - 1;
    while (l < r) {
        if (ss[l].toLowerCase() !== ss[r].toLowerCase()) {
            return false;
        }
        l++;
        r--;
    }
    return true;
};

时间复杂度：O(n)，空间复杂度：O(n)（构建了过滤后的字符串）

给植物浇水 II

• 相向双指针模拟：Alice 从左、Bob 从右同时浇水
• 水不够时补满再浇（注意是加满，不是累加剩余）
• 踩坑：l === r 时需要单独判断谁来浇（优先 Alice，再 Bob，都不够就补水）
• 核心调试思维：跟踪"状态变化"——什么变了、怎么变的、变之前还是变之后用旧值

/**
 * @param {number[]} plants
 * @param {number} capacityA
 * @param {number} capacityB
 * @return {number}
 */
var minimumRefill = function (plants, capacityA, capacityB) {
    //很明显的相向双指针了，要标记容量，模拟即可
    let ca = capacityA, cb = capacityB;
    let l = 0, r = plants.length - 1;

    let ans = 0;
    while (l < r) {
        if (ca >= plants[l]) ca -= plants[l++];
        else {
            ans++;
            //注意这里是加满，前面剩的不累加
            ca = capacityA - plants[l]
            l++;
        }
        if (cb >= plants[r]) cb -= plants[r--];
        else {
            ans++;
            cb = capacityB - plants[r]
            r--;
        }
        if (l === r) {
            if (ca >= plants[l]) break;
            else if (cb >= plants[l]) break;
            else ans++;
        }
        //可以优化成满足条件++；
    }
    return ans;
};

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

附录

正则表达式基础

1. 字符组 []

方括号表示匹配其中的任意一个字符：

• [abc] - 匹配 a、b 或 c 中的任意一个
• [a-z] - 匹配任意小写字母（a 到 z）
• [0-9] - 匹配任意数字（0 到 9）
• [a-zA-Z] - 匹配任意大小写字母

2. 反向字符组 [^]

在方括号内开头使用 ^ 表示取反，匹配不在括号内的字符：

• [^a-z] - 匹配任何不是小写字母的字符
• [^0-9] - 匹配任何不是数字的字符
• [^a-zA-Z0-9] - 匹配任何不是字母和数字的字符

3. 量词 +

• + 表示前面的模式出现一次或多次
• 例如：/a+/ 可以匹配 "a"、"aa"、"aaa" 等

4. 修饰符 g 和 i

• g 表示全局匹配，不只是匹配第一个
• i 表示忽略大小写

/abc/.test('ABC');   // false（区分大小写）
/abc/i.test('ABC');  // true（忽略大小写）

const str = 'a1b2c3';
str.match(/\d/);     // ["1"]（只找第一个数字）
str.match(/\d/g);    // ["1","2","3"]（找所有数字）

5. 分解 /[^a-z0-9]/g

/[^a-z0-9]/g

// 分解：
/           // 正则表达式的开始
[^          // 匹配任何不在以下字符组中的字符
a-z         // 小写字母 a 到 z
0-9         // 数字 0 到 9
]           // 字符组结束
/           // 正则表达式结束
g           // 全局匹配修饰符

6. 实际应用

const s = "A man, a plan, a canal: Panama";

// 先转小写，再用正则替换
const filtered = s.toLowerCase().replace(/[^a-z0-9]/g, '');
// "amanaplanacanalpanama"

// 只保留数字
"abc123def456".replace(/[^0-9]/g, '');     // "123456"

// 只保留字母
"abc123def456".replace(/[^a-zA-Z]/g, '');  // "abcdef"

// 只保留中文
"Hello 你好 123".replace(/[^\u4e00-\u9fa5]/g, '');  // "你好"

// 移除所有空格
" a b c ".replace(/\s/g, '');              // "abc"

// 检查是否只包含字母数字
/^[a-zA-Z0-9]+$/.test("abc123");           // true
/^[a-zA-Z0-9]+$/.test("abc 123");          // false（包含空格）

// 提取所有单词
"Hello, world! 123".match(/[a-zA-Z]+/g);   // ["Hello", "world"]

常用正则速查表

模式	含义
\d	数字，等价于 [0-9]
\D	非数字，等价于 [^0-9]
\w	单词字符（字母、数字、下划线），等价于 [a-zA-Z0-9_]
\W	非单词字符
\s	空白字符（空格、制表符等）
\S	非空白字符
.	匹配除换行符外的任意字符

// 用 \d 简化
"abc123".replace(/\D/g, '');    // "123"（保留数字）
"abc123".replace(/\d/g, '');    // "abc"（移除数字）

// 用 \w 简化
"hello_world!@#".replace(/\W/g, '');  // "hello_world"