一、题目
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
二、示例
2.1> 示例：
【输入】["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
【输出】[null,1,1,1,2,1,4,6]
【解释】首先，初始化 S = StockSpanner()，然后：S.next(100) 被调用并返回 1，S.next(80) 被调用并返回 1，S.next(60) 被调用并返回 1，S.next(70) 被调用并返回 2，S.next(60) 被调用并返回 1，S.next(75) 被调用并返回 4，S.next(85) 被调用并返回 6。
【注意】 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格(包括今天的价格 75) 小于或等于今天的价格。
提示：
- 调用 StockSpanner.next(int price) 时，将有
1<= price <=10^5。 - 每个测试用例最多可以调用
10000次 StockSpanner.next。 - 在所有测试用例中，最多调用
150000次 StockSpanner.next。 - 此问题的总时间限制减少了 50%。
三、解题思路
3.1> 利用堆栈实现
首先，根据题目描述，我们发现只有股票趋势是下降的情况下，才会统计跨度日期，所以我们首先可以利用堆栈来进行跨度日期的计算。堆栈操作有如下3种情况：
【情况1】如果堆栈为空，则直接入栈；
【情况2】如果“栈顶元素”的price大于“输入股票”的price，则输入股票入栈；
【情况3】如果“栈顶元素”的price小于等于“输入股票”的price，则将“栈顶元素”出栈，并将“栈顶元素”的day值加到“输入股票”的day值上。然后再对比下一个“栈顶元素”，操作以此类推，直到发现当前的“栈顶元素”大于了“输入股票”的price，则将“输入股票”入栈即可。
具体操作，请见下图所示：
4.2> 利用数组+指针实现
第二种方式，我们采用两个数组，分别是prices用来记录股票价格和days用来记录跨度天数。那么针对于第n次输入的股票，它的价格和跨度天数就是prices[n]和days[n]。
除了prices和days这两个数组之外，我们还需要两个指针，分别是index指针，用来指向“待输入股票”；p指针，index指针的前一个指针，用来与“待输入股票”进行price对比用的，如果它的price小于等于“待输入股票”的price，p就会向前移动。
关于p向前移动还有一点需要注意的就是，p向前移动格子的数量，就是days的具体值；当days等于1时，就向前移动1个格子；如果days等于2时，就向前移动2个格子（因为days等于2，说明已经是两个格子聚合过的值了，就不需要重复统计了）。具体操作，请见下图所示：
四、代码实现
4.1> 利用堆栈实现
class StockSpanner {
Deque<Stock> deque;
public StockSpanner() {deque = new ArrayDeque();}
public int next(int price) {
int day = 1;
while (!deque.isEmpty() && deque.peekLast().price <= price)
day += deque.removeLast().day;
deque.addLast(new Stock(price, day));
return day;
}
class Stock {
public int price;
public int day;
public Stock(int price, int day) {
this.price = price;
this.day = day;
}
}
}
4.2> 利用数组+指针实现
class StockSpanner {
int index = 0; // index：待插入的位置
int[] prices, days; // 价格列表和跨度天数列表，同一下标，一一对应关系
public StockSpanner() {
prices = new int[10000];
days = new int[10000];
index = 0;
}
public int next(int price) {
int p = index - 1; // 待对比的位置
while (p >= 0 && prices[p] <= price) p -= days[p]; // 向前移动p
prices[index] = price;
days[index] = index - p;
return days[index++]; // index加1
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论