-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathStockSpan.java
More file actions
71 lines (63 loc) * 2.33 KB
/
StockSpan.java
File metadata and controls
71 lines (63 loc) * 2.33 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package Leetcode;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* @author kalpak
*
* 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","n ext"], [[],[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 have 1 <= price <= 10^5.
* There will be at most 10000 calls to StockSpanner.next per test case.
* There will be at most 150000 calls to StockSpanner.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.
*/
public class StockSpan {
Deque<int[]> stack;
public StockSpan() {
stack = new ArrayDeque<>();
}
public int next(int price) {
int span = 1;
while(!stack.isEmpty() && stack.peek()[0] <= price) {
span += stack.poll()[1];
}
stack.push(new int[]{price, span});
return span;
}
public static void main(String[] args) {
StockSpan obj = new StockSpan();
System.out.println(obj.next(100));
System.out.println(obj.next(80));
System.out.println(obj.next(60));
System.out.println(obj.next(70));
System.out.println(obj.next(60));
System.out.println(obj.next(75));
System.out.println(obj.next(85));
}
}