单调队列·应用

8 分钟

除了滑动窗口最值,它还能优化某些 DP:当转移是“在一段滑动区间里取最优”时,用单调队列把每步 O(k) 降到均摊 O(1),这类叫单调队列优化 DP。

小纸条

求窗口最小值时,队尾应弹出哪些元素?

登录 后可看答案