Joey LIU | NANTSOU


 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
/**
 * key point is to store local maximum span (price, days) to reduce the time of calculating the days.
 * ex. [100, 80, 60, 70, 60, 75, 85]
 * => [(100, 1), (80, 1), (70, 2), (85, 3)]
 */
class StockSpanner {
    
    List<Pair> stock;
    
    public StockSpanner() {
        stock = new ArrayList<>();
    }
    
    public int next(int price) {
        int span = 1;
        while (stock.size() > 0) {
            Pair pair = stock.get(stock.size() - 1);
            if (pair.price > price) {
                stock.add(new Pair(price, span));
                return span;
            } else {
                span += pair.span;
                stock.remove(stock.size() - 1);
            }
        }
        stock.add(new Pair(price, span));
        return span;
    }
    
    class Pair {
        int price;
        int span;
        
        public Pair(int price, int span) {
            this.price = price;
            this.span = span;
        }
    }
}