单调栈

[Ir1d]

https://oi-wiki.org/ds/monotonous-stack/

[lucheng2]

个人感觉这里对单调栈要解决的最基础的问题没有表述清楚，加上poj的这道例题的配图有点问题，导致看的时候走了些许弯路。建议学习的小伙伴先解决洛谷上的单调栈模板题，再回头来做poj的这道题，相信对单调栈的理解会深入许多。模板题传送门：https://www.luogu.com.cn/problem/P5788

[ShizuhaAki]

每个元素最多入一次出一次，复杂度是线性的

[ferapontqiezi]

@lucheng2
个人感觉这里对单调栈要解决的最基础的问题没有表述清楚，加上poj的这道例题的配图有点问题，导致看的时候走了些许弯路。建议学习的小伙伴先解决洛谷上的单调栈模板题，再回头来做poj的这道题，相信对单调栈的理解会深入许多。模板题传送门：https://www.luogu.com.cn/problem/P5788

支持

[Edward-Elric233]

使用单调栈解决离线RMQ问题的时间复杂度是否应该再加上O(n)的单调栈遍历？

[arong]

POJ3250 Bad Hair Day 这道题在洛谷上面也有: P2866 [USACO06NOV]Bad Hair Day S

[NotTogawaButSakiko]

单调栈求离线RMQ问题的复杂度显然为 $O(q \log q + n \log n)$

[Yerosius]

个人认为对于RMQ问题离线+单调栈的做法非常不严谨，单调栈是基于栈的数据结构，栈不支持随机访问，怎么可能能够二分

[Yerosius]

只是用到了单调栈的思想，但却说这就是“单调栈”，未免也有点太不严谨了吧