7. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子下雨后能接多少雨水。
height=[0,1,0,2,1,0,1,3,2,1,2,1] → 返回 6。
提示
默认收起。卡住时一层一层看，不直接泄露答案。
约束与边界
- 输入满足题目给出的类型与取值约束。
- 边界提醒：不是比较 lmax 与 rmax 后随便走；要明确哪一侧的上限已经确定。
第 7 题 / 共 61 题
接雨水
Hard 双指针 11 步推演
较矮且已确认的一侧决定当前格水位，可以立刻结算。
- 复杂度
- 时间 O(n),空间 O(1)。
- 示例输出
- 6
FINAL SOLUTION 答案代码与下方推演同步高亮
TypeScript Worker 内转译并隔离运行
等待运行 尚无结果
- 实际输出
- -
- 期望输出
- -
- 耗时
- -
HOW TO THINK · 61 题反推
拿到一道新题，先怎么想
难点常常不在代码，而在第一步往哪走。先认清题目允许的动作，再看答案要什么；接着找能否持续排除候选，最后用数据规模检查这条路是否跑得动。
对象
数据天然长什么样？
数组、连续区间、链表、树和依赖图，允许的移动方式不同。 目标
要找一个、找最优、计数，还是列出全部？
同一份输入，输出目标不同，解法可能从哈希表切换到回溯或动态规划。 推进
移动一步后，能永久排除一批候选吗？
能单调排除，才有资格用双指针、滑动窗口或二分。 规模
n 的量级允许 O(n²)、O(2ⁿ) 还是只能 O(n)？
规模不是边角条件，它会直接否决不可能通过的算法。 正在判断 01
题目最明显在操作什么？
先认清数据关系，因为它决定你能怎样移动、访问和保存状态。
PATTERN LIBRARY
18 种常用思路，不是 61 份答案
题目反复问“见过吗、出现几次、搭档在哪”。
我不回头扫描，只维护过去足够回答未来的问题。两端、两路、有序配对，或一次移动能永久排除一侧。
每移动一次，都要说清为什么被丢掉的一整片再也不用看。连续子串 / 子数组，长度 K 已知，每轮只进一个、出一个。
右边进一个，左边出一个，别重新统计整段。连续段最长 / 最短，窗口是否合格能随左右边界增量判断。
先扩到条件变化，再只用左边界恢复或压紧条件。大量区间聚合、除自身、到当前位置为止的累计信息。
先问：走到 i 时，过去到底只需要留下哪一个摘要？输入是 [start,end]，问重叠、合并、冲突或覆盖。
先排序，把全局混乱变成只看邻居。最近打开、成对闭合、嵌套结构、撤销最近动作。
新的未完成任务压顶，只有最上面的能先结束。每个位置右边 / 左边第一个更大、更小，或可见边界。
栈里只留还没等到答案的人。有序数据，或答案可行性呈单调真假分界。
别问 mid 像不像答案，要问 mid 能证明哪半边不可能。要求原地反转、删除、合并，不能随机访问。
每次改箭头前，先说清手里是否还握着后半条链。无权最短步数、层序、同时扩散、多源最近距离。
进入一层前锁住队列长度，这层就是同一时刻。连通块、存在路径、树的子问题向父节点返回信息。
先定义递归函数返回什么，当前节点只负责组合孩子的答案。课程、任务或构建存在前置依赖，问能否完成或合法顺序。
每完成一个前置，就把后继欠的依赖减一。要求所有排列、组合、合法路径，输入规模通常很小。
选择 → 递归 → 撤销；剪枝只删掉不可能成功的分支。求最优或计数；问题能拆成重复子问题，当前答案来自有限前驱。
先用一句人话定义 dp[i] 或 dp[i][j]，再写转移。每一步只需保留最有前途的边界，且能证明错过的选择不会翻盘。
说清局部选择为什么不会让全局最优消失。持续加入数据，同时反复取最小、最大或只保留前 K。
堆里只放有资格竞争下一名的候选。题目同时要求两种单一结构无法兼得的 O(1) 操作。
先拆职责：谁负责找，谁负责顺序，更新时怎么保持一致。覆盖不了的，不要硬塞进大类
回文围绕中心对称，答案不是普通窗口单调收缩。
一个序列给根顺序，另一个序列负责切分左右结构。
Trie、并查集、位运算、带权最短路、线段树等应作为后续扩展，不硬塞进现有 61 题。