知识卡片

普通读书笔记卡 · 5626.g.1.c

容器双指针舍去受限短边

理解等级:中级

两端隔板形成的面积等于较短高度乘间距。检查当前面积后,若左端较短,保留它而向内移动右端只会缩宽,且高度仍被左端限制,不能超过已检查面积,因此可舍去这条左端。

对称处理另一边,每轮至少移一个指针,线性时间遍历。需要非负高度和安全整数乘法;被跳过状态可能与当前并列最优,正确依据是不更优,不是绝不最优。原书float64转换对大整数也有精度限制。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      这些被跳过的状态实际上就是将长板 向内移动的所有状态 。前面我们已经证明内移长板一定会 导致容量变小。也就是说,被跳过的状态都不可能是最优解,跳过它们不会导致错过最优解 。 以上分析说明,移动短板的操作是“安全”的,贪心

    参考来源

    - 位置:《Hello 算法--Go版本》第15章《贪心》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/8.html;spine 7,归一字符[9738,9848)) - 结论依据:实际短边移动/跳过状态证明及代码,修正零高/同值严格变小。 - 原始内容:这些被跳过的状态实际上就是将长板 向内移动的所有状态 。前面我们已经证明内移长板一定会 导致容量变小。也就是说,被跳过的状态都不可能是最优解,跳过它们不会导致错过最优解 。 以上分析说明,移动短板的操作是“安全”的,贪心