Day 21。
今天两道题分别是 Trapping Rain Water 和 Multiply Strings。
一道是非常经典的 双指针接雨水题，一道是典型的 字符串模拟乘法题。

今天的关键词：双指针、左右最大值、按位乘法、进位处理、数组模拟。

🧠 LeetCode 42 – Trapping Rain Water

💡 思路总结

这题要求计算柱状图下雨之后能接多少水。
核心规律其实就一句话：

某个位置能接多少水，取决于它左边最高柱子和右边最高柱子中较小的那个。

公式可以理解成：

water[i] = min(left_max, right_max) - height[i]

你的思路用的是经典双指针写法：

  • 左指针从左往右
  • 右指针从右往左
  • 维护 left_max 和 right_max
  • 每次处理较矮的一边

这个思路本身是对的，而且是这题非常高频的正解。

💻 代码实现

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0;
        int right = height.size()-1;
        int left_max;
        int right_max;
        int result = 0;
        while(right>left){
            if(height[left] < height[right]){
                if(height[left]>left_max){
                    left_max = height[left];
                }
                else{
                    result += left_max - height[left];
                }
                left++;

            }
            else{
                if(height[right]>right_max){
                    right_max = height[right];
                }else{
                    result += right_max - height[right];
                }
                right--;

            }
        }
        return result;
    }
};

📌 知识点总结

1️⃣ 为什么可以处理较矮的一边

这题双指针的核心逻辑是：

  • 如果 height[left] < height[right]
  • 那么当前左边位置能不能接水，只需要看 left_max

因为右边已经至少有一个比左边高的柱子存在，所以这时候限制左边接水量的，是左边目前的最高值。

反过来，如果右边更矮，就处理右边。

所以这题的本质不是“随便双指针”，而是：

谁矮先处理谁

2️⃣ left_max 和 right_max 的意义

你这里维护的是：

  • left_max：从左边走到当前位置时，见过的最高柱子
  • right_max：从右边走到当前位置时，见过的最高柱子

当某一边当前柱子低于对应最大值时，就能接水：

result += left_max - height[left];

或者：

result += right_max - height[right];

3️⃣ 这里有一个重要 bug

你这份代码思路是对的，但有个关键问题：

int left_max;
int right_max;

这两个变量没有初始化。
C++ 里局部变量如果不初始化，值是未定义的，这会导致结果错误。

更稳的写法应该是：

int left_max = 0;
int right_max = 0;

✅ 更稳一点的版本

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int left_max = 0;
        int right_max = 0;
        int result = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    result += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    result += right_max - height[right];
                }
                right--;
            }
        }

        return result;
    }
};

4️⃣ 这题是双指针题里的代表作

这题很经典，因为它不是简单夹逼，而是：

  • 一边移动
  • 一边维护状态
  • 一边计算贡献

它非常能体现双指针题的“动态维护信息”能力。

✖️ LeetCode 43 – Multiply Strings

💡 思路总结

这题要求实现两个非负整数字符串相乘，不能直接转成大整数类型。
所以本质上就是：

模拟小学竖式乘法

你的思路是标准写法：

  1. 开一个长度为 n1 + n2 的数组 res
  2. 从后往前枚举 num1[i] 和 num2[j]
  3. 计算当前位乘积
  4. 累加到结果数组对应位置
  5. 最后把前导零去掉，转成字符串

这题非常经典。

💻 代码实现

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size(),n2 = num2.size();
        vector<int> res(n1+n2,0);
        for(int i = n1-1;i>=0;i--){
            for(int j = n2-1;j>=0;j--){
                int mul = (num1[i]-'0')*(num2[j]-'0');
                int sum = mul + res[i+j+1];
                res[i+j+1] = sum%10;
                res[i+j] += sum/10;
            }
        }
        string result;
        for(int num  : res){
            if(!(result.empty() && num == 0)){
                result.push_back(num + '0');
            }
        }
        return result.empty() ? "0" : result;

    }
};

📌 知识点总结

1️⃣ 为什么结果长度最多是 n1 + n2

如果一个数有 n1 位，另一个数有 n2 位，乘积最多只有：

n1 + n2 位

比如：

  • 99 × 99 = 9801，2 位乘 2 位，最多 4 位

所以你开：

vector<int> res(n1 + n2, 0);

是完全正确的。

2️⃣ 下标位置为什么是 i+j 和 i+j+1

这是这题最关键的细节。

假设：

  • num1[i] 和 num2[j] 相乘
  • 它们对应的结果位置会落在 res[i+j+1]
  • 进位加到 res[i+j]

这和竖式乘法的位数对齐是一样的。

所以这两句是灵魂：

res[i+j+1] = sum % 10;
res[i+j] += sum / 10;

3️⃣ 先加旧值再处理进位

你这里写的是：

int sum = mul + res[i+j+1];

这一步非常重要。
因为当前位置可能已经被之前别的乘积贡献过了，所以不能只看当前乘法结果，必须把原来的值也加进来。

4️⃣ 最后要去掉前导零

因为结果数组长度是按最大可能长度开的，所以前面可能会有零。
你这里通过：

if(!(result.empty() && num == 0))

跳过前导零，最后再处理全零情况：

return result.empty() ? "0" : result;

这个收尾很标准。

5️⃣ 这题本质是“数组模拟大整数”

虽然题目是字符串相乘，但真正底层做的事情是：

用数组保存每一位，模拟大整数运算

这类题以后在加法、乘法、阶乘、字符串数字处理里都很常见。

🧩 今日总结

题目核心思想
LeetCode 42双指针 + 左右最大值维护 + 接雨水计算
LeetCode 43竖式乘法模拟 + 数组存位 + 进位处理

今天两题风格差别很大：

  • 42 偏双指针与状态维护
  • 43 偏字符串与数位模拟

但它们都很经典，而且都属于高频模型题。

🧠 今日收获

今天最值得记住的两个模型：

1. 动态维护信息的双指针模型

如果题目里：

  • 左边信息和右边信息都重要
  • 每移动一步都要维护某个状态

那就要想到：

  • 双指针
  • 左右状态量
  • 边走边更新答案

2. 大整数模拟模型

如果题目要求：

  • 不能直接转整数
  • 要处理很长的数字字符串
  • 涉及逐位运算

那就要想到：

  • 用数组存每一位
  • 从低位往高位处理
  • 手动维护进位

💬 写给自己的话

Day 21 了。

三周了。

你现在已经不只是碰基础模板了，
而是在慢慢接触越来越多“非常经典”的代表题：

  • 接雨水
  • 字符串乘法
  • 原地哈希
  • 数独回溯
  • 旋转数组二分

这些题真的很有价值。
因为它们不是单一知识点，而是会让你慢慢建立起一种感觉：

看到题，就能大概判断它属于哪种模型。

这就是题感。

继续保持。
你现在做的每一道题、写的每一篇总结，都在帮你把这些模型变成自己的东西。

阿玉，Day 21，继续冲。

—— 刷题第 21 天