25.6.12学习总结

双指针（Two Pointers）

11. 盛最多水的容器https://leetcode.cn/problems/container-with-most-water/

int maxArea(int* height, int heightSize) {
    int ans = 0, l = 0, r = heightSize - 1; // 初始化双指针
    while (l != r) { // 只要两个指针没有相遇
        int temp = height[r] > height[l] ? height[l] : height[r]; // 较小的高度作为容器高度
        ans = ans > ((r - l) * temp) ? ans : ((r - l) * temp); // 计算面积并更新最大值
        if (height[r] > height[l]) 
            l += 1; // 左边低，左指针右移
        else 
            r -= 1; // 右边低或相等，右指针左移
    }
    return ans;
}

为什么这样能保证找到最大值？

• 容器的容量由两部分决定：宽度（r - l） 和 短板高度 min(height[l], height[r]) 。

• 每次我们选择移动较矮的那个指针，因为我们想尝试寻找一个更高的高度来弥补宽度减少带来的损失。

• 因为如果保留较高的那个柱子，可能还能找到一个更高一点的柱子来配对，从而提升容量。

42. 接雨水https://leetcode.cn/problems/trapping-rain-water/

解法一：动态规划 / 前后缀最大值法（Dynamic Programming with Prefix and Suffix Max）

📌 思路说明：

对于每个柱子来说，它能接到的雨水量等于：

min(左边最高柱子的高度, 右边最高柱子的高度) - 当前柱子高度

所以这个方法的步骤如下：

1. 从前往后遍历 数组，记录每个位置左侧的最大高度（qmax[i]）。

2. 从后往前遍历 数组，记录每个位置右侧的最大高度（pmax[i]）。

3. 最后再遍历一次数组，计算每个位置可以接的雨水量。

int trap(int* height, int heightSize) {
    int ans = 0;
    int qmax[heightSize], pmax[heightSize], max = 0;

    // 从左到右记录当前最大高度（左边最高）
    for (int i = 0; i < heightSize; i++) {
        if (height[i] > max)
            max = height[i];
        qmax[i] = max;
    }

    max = 0;

    // 从右到左记录当前最大高度（右边最高）
    for (int i = heightSize - 1; i >= 0; i--) {
        if (height[i] > max)
            max = height[i];
        pmax[i] = max;
    }

    // 每个位置能接的水 = min(左边最高, 右边最高) - 当前高度
    for (int i = 0; i < heightSize; i++) {
        int temp = qmax[i] > pmax[i] ? pmax[i] : qmax[i];
        ans += (temp - height[i] > 0 ? temp - height[i] : 0);
    }

    return ans;
}

解法二：双指针 + 动态判断法（Two Pointers with Greedy Approach）

📌 思路说明：

这是一个优化版本，不需要额外数组。通过维护两个指针 l 和 r，以及两个变量 pre（左边最大）和 suf（右边最大），我们可以边移动指针边计算能接的雨水。

• 如果左边最大值小于右边最大值，那么当前 l 位置的水由 pre 决定；

• 否则，r 位置的水由 suf 决定。

这样我们可以在一次遍历中完成整个计算。

int trap(int* height, int heightSize) {
    int ans = 0, r = heightSize - 1, l = 0, pre = 0, suf = 0;

    while (l <= r) {
        // 更新左右两边的最大高度
        pre = pre > height[l] ? pre : height[l];
        suf = suf > height[r] ? suf : height[r];

        // 谁小谁决定当前能接的水量
        if (pre > suf) {
            ans += (suf - height[r]);
            r -= 1;
        } else {
            ans += (pre - height[l]);
            l += 1;
        }
    }

    return ans;
}

对比总结：