LC 901. Online Stock Span
2024-10-06 18:59:39
Write a class StockSpanner
which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.
The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.
For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85]
, then the stock spans would be [1, 1, 1, 2, 1, 4, 6]
.
Example 1:
Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation:
First, S = StockSpanner() is initialized. Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6. Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.
Note:
- Calls to
StockSpanner.next(int price)
will have1 <= price <= 10^5
. - There will be at most
10000
calls toStockSpanner.next
per test case. - There will be at most
150000
calls toStockSpanner.next
across all test cases. - The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.
Runtime: 225 ms, faster than 32.65% of Java online submissions for Online Stock Span.
class StockSpanner {
private Stack<Integer> s;
private List<Integer> alist;
private int cnt;
public StockSpanner() {
s = new Stack<>();
alist = new ArrayList<>();
cnt = ;
} public int next(int price) {
while( !s.empty() && alist.get(s.peek()) <= price ){
s.pop();
}
int tmpval;
if(!s.empty()) tmpval = s.peek();
else tmpval = -;
s.add(cnt);
alist.add(price);
cnt++;
return s.peek() - tmpval;
}
}
another solution
class StockSpanner {
List<Stock> stocks = new ArrayList<>();
public StockSpanner() {
// prices = new ArrayList<>();
// counts = new ArrayList<>();
} public int next(int price) { // Need to search backwards for the next highest price
int count = ;
// int countIndex = size-1; // int countIndex = size-1;
while(stocks.size() >= count) {
Stock s = stocks.get(stocks.size() - count);
if (s.price > price) {
break;
} else {
count += s.count;
}
}
stocks.add(new Stock(price, count));
// counts.add(count);
return count;
} class Stock {
int price;
int count; public Stock(final int price, final int count) {
this.price = price;
this.count = count;
}
} }
最新文章
- instanceof
- 我的 GitHub 100 连击
- jquery 常用的备忘
- 【原】SQL ROW_NUMBER() OVER
- MySQL数据库优化技术之SQL语句慢查询定位
- Mongodb地理空间索引
- WPF MVVM 中怎样在ViewModel总打开的对话框在窗体之前
- [C#]『PLINQ』任务并行库使用小计
- Spring4.3.1 JDBCTemplate操作数据库
- 服务器编程入门(1)TCP/IP协议族
- oracle常用高级sql---1
- C语言尝试在不同源文件中调用程序段
- Kubernetes 学习1 k8s架构概述
- SpringBoot集成Shiro安全框架
- request请求转换成对象。
- 从一个Idea到产品需要经历哪些阶段?
- 【转】ubuntu中没有/etc/inittab文件探究
- TPS和QPS定义以及影响TPS的因素
- 总结day26 ----验证客户端的合法性,已经操作系统,进程的简单初识别
- 经典Mathematica函数大全