LC 42
Trapping Rain Water
Hard · LC 1–100
候选解法路线
Primary
Free单调栈找最近更大/更小
Invariant: 栈中索引递增，值按指定方向单调；栈内每个索引都尚未遇到能解决它的右侧元素。
candidate confidence: 0.700 · metadata_only
Alternate 1
Free栈式状态模拟
Invariant: 处理完输入前缀后，栈自底向上按开启顺序保存所有尚未完成的上下文；栈顶是下一 token 唯一可直接影响的最近上下文。
candidate confidence: 0.488 · metadata_only
Alternate 2
Free线性 DP / 一维状态递推
Invariant: 计算完 i 后，所有不超过 i 的状态都等于其定义下的真实最优值/计数；任何未来转移只读取这些已完成状态。
candidate confidence: 0.470 · metadata_only
如何使用本页
先读原题与 constraints，再逐一验证 Recognition signals、invariant 与 complexity；candidate score 不能证明正确性。