博客 · 第 8 页
关于工程、设计与一些随手记录。
滑动窗口：先定「窗口里维护什么」，再写循环
窗口能成立的前提是「窗口是否合法」随左右边界单调。先写下维护的状态与收缩条件，双指针的两层循环自然会摊还成 O(n)。
单调栈：把「下一个更大的数」从 O(n²) 拉回 O(n)
每个元素最多进栈一次、出栈一次，所以看起来是双层循环的写法其实是线性。认出「左右第一个比自己大/小」这个形状，就能套同一个模板。
数二进制里有多少个 1：从循环到 SWAR
popcount 有三种写法：按 1 的个数循环、查表、以及并行算位的 SWAR。三种复杂度差一个数量级，而 Rust 与 WebAssembly 已经把它做成了单条指令。
并查集：两行优化让每次操作几乎变成常数
路径压缩把树压平，按大小合并让树不会长高。两个都要，复杂度才落到反阿克曼函数上 —— 也就是说 10 亿次操作也不会慢。
Rust 的 Result 里，上下文要补在出错的那一层
`?` 会把错误原样上抛，不告诉你在哪一步失败。底层返回可匹配的结构化错误，应用层用 Context 补上「在做什么」和输入参数，日志里才有能定位的那一行。
什么时候该把一个 crate 拆成 workspace
拆 workspace 的触发条件是编译时间和依赖边界，不是目录好不好看。三个信号成立才拆，否则只是把一次编译换成多个包的管理成本。