股票价格跨度

题目链接

股票价格跨度

题目描述

注意

• 今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

解答思路

• 分别保存每个位置处的股票价格以及该股票价格的跨度，在求某一天股票价格的跨度时，如果前一天的股票价格比当天的股票价格高，则返回1，否则需要根据前一天股票价格的跨度求得今天的跨度（注意并不是前一天的跨度+1，因为在可能会有比前一天的股票价格高但是比今天的股票价格低的存在，所以还需要再对前一天跨度之前的股票价格进行判断）

代码

方法一：

class StockSpanner {
    // 存储某处股票位置以及该股票价格的跨度
    Map<Integer, Integer> map;
    // 存储某处股票位置以及对应的股票价格
    List<Integer> list;
    int i = 0;
    public StockSpanner() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }
    
    public int next(int price) {
        list.add(price);
        int idx = i - 1;
        int sum = 1;
        while(idx >= 0 && list.get(idx) <= price) {
            sum += map.get(idx);
            idx -= map.get(idx);
        }
        map.put(i, sum);
        i++;
        return sum;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */
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

关键点

• 股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天），注意连续