解题思路
能否利用之前的计算结果来优化？答案是肯定的。
算法
使用数组存储股票价格及其对应的跨度。
当新价格小于前一日价格时，可直接利用之前计算的跨度结果，避免重复计算。
复杂度分析
Git
程序猿必备版本控制工具
下载
时间复杂度：O(n) 每次
操作最坏情况下遍历整个数组，但平均时间复杂度为O(1)。
空间复杂度：O(n) 存储价格和跨度的数组大小与输入数据量成正比。
代码实现
GitHub 仓库及 LeetCode 链接
更多解法请访问 GitHub 仓库：
GitHub 仓库链接
LeetCode 题目链接：
LeetCode 题目链接
(devn007)
nextimport java.util.ArrayList;
import java.util.List;
class StockSpanner {
List list;
public StockSpanner() {
list = new ArrayList<>();
}
public int next(int price) {
int span = 1;
int index = list.size() - 1;
while (index >= 0 && list.get(index)[0] <= price) {
span += list.get(index)[1];
index -= list.get(index)[1];
}
list.add(new int[]{price, span});
return span;
}
}
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner obj = new StockSpanner();
* int param_1 = obj.next(price);
*/