题解
\(O(n^3)\) 的暴力方法：
遍历所有区间，然后找出每个区间内的最小值
\(O(n^2)\) 的暴力方法：
考虑每个点的贡献，往左扩展直至出现比其小，往右扩展直至出现比其小的
观察 \(O(n^2)\) 的暴力方法，我们发现往左扩展和往右扩展相互独立
所以我们只观察往左扩展
”往左扩展直至遇见比自己小的“ 这个不就是找到左边第一个比自己小的这样一个经典 的问题吗？
如果一个选手年龄比你小还比你强，那你可以退役了，也就是说，我们不需要每次遍历其左边所有元素
考虑当前数需要遍历的决策点，如果存在某个决策点，其左边的数比自己大，那么左边这个数就是无用决策点，可以删除
这样一来，当前数需要考虑的决策点是一个从左往右下标递增，数的大小递增的序列
如果序列的末尾数比当前数大，那么就删除，因为不会对后面的答案产生贡献，如果比自己小，那么这个数就是当前数的左边第一个比自己小的的数
然后把当前数插入决策点序列
这样一来，时间复杂度就是 \(O(n)\)
标签：遍历,暴力,左边,Sum,扩展,决策,Minimum,当前 From： https://www.cnblogs.com/pure4knowledge/p/18353237