我在用栈维护凸壳时,还维护了一个最优决策点,单调队列的队头是不是类似这个决策点
by Edgebright @ 2023-07-04 22:00:24
其实 Andrew 算法用的是单调栈,维护凸壳用的也是单调栈。
那个单调队列本质上就是两个指针,尾指针起到单调栈的作用维护凸壳,头指针在斜率单调时起到均摊 $O(n)$ 更新答案的作用。
by TKXZ133 @ 2023-07-05 08:07:47
@[Edgebright](/user/762588) 是这样的
by TKXZ133 @ 2023-07-05 08:09:05
@[TKXZ133](/user/767096) 谢谢大佬
by Edgebright @ 2023-07-05 08:23:21