题目描述

小友正在优化财务报表分析功能。给定一个由不同整数构成的数组revenues，每个元素表示在不同时间段内的收入。我们用以下方式定义一个与revenues长度相同的数组maxDurations:

$maxDurations[i]$是一个子数组 $revenues[l..r]$的最大长度，该子数组中的最大收入等于$revenues[i]$。

思路：单调栈

对于一个值$x$，我们需要找到其两边比$x$大的第一个值。

使用单调递减栈可以实现该目标。栈中每个元素的左边是比该元素大的第一个值。而当一个元素出栈时，那么其右边第一个比其大的值也就找到了。

时间复杂度为$O(N)$