曾经从2元涨到100元的股票(曾经从2元涨到100元的股票叫什么)

一句话题意

求出每个 price 的上一个更大元素，距离当前有多远。

题意

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。

当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

• 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

• StockSpanner() 初始化类对象。
• int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

示例：

提示：

• 1<=price<=10^5
• next 方法 最多调用 10^4次

解题思路

• 考虑next方法最多调用10^4，可以2层for循环解决，O(n^2)

• 用单调栈解决，保证栈顶的元素值，始终小于栈内相邻的元素值，O(n)