妙哉!Second Sum! 提供两种做法,一种是依赖于单调栈和 ST 表的 O(nlgn)\mathcal O(n \lg n)O(nlgn) 做法,思维难度较低;还有一个绝妙的做法,根本想不到,但不需要任何现成的 算法/数据结构, 时间复杂度 O(n)\mathcal O(n)O(n)。 传送门 2021-03-17 次阅读 6 min read