Acfboy 的博客

提供两种做法，一种是依赖于单调栈和 ST 表的 $\mathcal O(n \lg n)$ 做法，思维难度较低；还有一个绝妙的做法，根本想不到，但不需要任何现成的 算法/数据结构， 时间复杂度 $\mathcal O(n)$。

传送门