这篇博客介绍了如何利用单调栈解决区间最值问题，通过删除栈中第一个小于当前元素的值来找到最长高度为(h[i])的区间。此外，还提到了笛卡尔树这一数据结构在类似问题中的应用，帮助读者理解并掌握这两种高效算法。
表示之前还不会这种类型怎么快速求值。。。
\(Solution 1\)
我们可以维护一个单调栈，使得\(h\)是递增的。
每次到一个位置，删到前面第一个比它小的位置，记作\(k\)，然后最长的高度为\(h[i]\)的区间就是\([k+1,i]\)。
正着来一遍，再倒着来一遍即可。
扫一扫
评论
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
查看更多评论
添加红包
