LeetCode 解题报告 (739,901,907)- 线性时间寻找数组中各个元素作为最值的最大范围
题目有点拗口,其实就是给定一个数组,要求给出某个元素作为最小值或最小值的那些 continous subarrays 中最长的长度,如对于数组 [1, 2, 5, 6]
, 元素 5 作为最大值的 continous subarrays 有三个: [5], [2, 5], [1, 2, 5]
,长度最长的是 3。遍历的解法找出一个元素要 \(O(n)\) 的时间复杂度,找出所有元素则需要 \(O(n^2)\) 的时间复杂度,而通过栈能够在 \(O(n)\) 的时间复杂度内解决这个问题。