901. 股票价格跨度
难度: 中等
来源: 每日一题 2023.10.07
设计一个算法收集某些股票的每日报价,并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始往回数,包括今天)。
例如,如果未来 7
天股票的价格是 [100,80,60,70,60,75,85]
,那么股票跨度将是 [1,1,1,2,1,4,6]
。
实现 StockSpanner
类:
StockSpanner()
初始化类对象。int next(int price)
给出今天的股价price
,返回该股票当日价格的 跨度 。
示例:
输入:
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出:
[null, 1, 1, 1, 2, 1, 4, 6]
解释:
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80); // 返回 1
stockSpanner.next(60); // 返回 1
stockSpanner.next(70); // 返回 2
stockSpanner.next(60); // 返回 1
stockSpanner.next(75); // 返回 4 ,因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85); // 返回 6
提示:
1 <= price <= 10^5
- 最多调用
next
方法10^4
次
class StockSpanner {
public StockSpanner() {
}
public int next(int price) {
}
}
分析与题解
-
暴力法
暴力方案就很简单了, 我们只需要按照题目要求创建一个数组空间用来存储每日的价格, 要求该股票当日价格的 跨度 , 我们只需要倒序遍历即可.
代码如下所示.
class StockSpanner { List<Integer> cache = new ArrayList<>(); public StockSpanner() { } public int next(int price) { int result = 1; for(int i = cache.size() - 1; i >= 0; i--) { if(cache.get(i) <= price) { result++; } else { break; } } cache.add(price); return result; } } /** * Your StockSpanner object will be instantiated and called as such: * StockSpanner obj = new StockSpanner(); * int param_1 = obj.next(price); */
复杂度分析:
- 时间复杂度: O(n²)
- 空间复杂度: O(n), 空间与数组的长度成线性关系.
结果如下所示.
-
暴力法优化
暴力方案其实很好理解了, 但是存在很多重复的遍历过程, 我们不妨考虑, 这样的一种情况, 当我们知道前面某天A的价格的 跨度, 那么如果后面某一天比A的价格还要高, 那么他的价格跨度区间同样适用于这一天. 如图所示.
这时候, 我们可以直接跳过A的所有跨度, 从而减少遍历的次数. 如下图所示.
那么我们在遍历过程中就可以增加这样的过程减少遍历次数, 但是我们需要另外创建一个数组用来保持某一天的跨度 .
List<Integer> resultArray = new ArrayList<>();
对于优化跳转的代码, 具体如下所示.
for(int i = cache.size() - 1; i >= 0; i--) { if(cache.get(i) <= price) { result += resultArray.get(i); i -= resultArray.get(i) - 1; } else { break; } }
接下来, 我们一起看一下整体的代码实现.
class StockSpanner { List<Integer> cache = new ArrayList<>(); List<Integer> resultArray = new ArrayList<>(); public StockSpanner() { } public int next(int price) { int result = 1; for(int i = cache.size() - 1; i >= 0; i--) { if(cache.get(i) <= price) { result += resultArray.get(i); i -= resultArray.get(i) - 1; } else { break; } } resultArray.add(result); cache.add(price); return result; } } /** * Your StockSpanner object will be instantiated and called as such: * StockSpanner obj = new StockSpanner(); * int param_1 = obj.next(price); */
复杂度分析:
- 时间复杂度: O(n²)
- 空间复杂度: O(2n), 空间与数组的长度成线性关系.
结果如下所示.
Comments | 0 条评论