LC.P901[股票价格跨度]

方法一：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class StockSpanner {

    List<Integer> list;

    public StockSpanner() {
        list = new ArrayList<>();
    }
    
    public int next(int price) {
        list.add(price);
        int ans = 0;
        for (int i = list.size() - 1; i >= 0; --i) {
            if (list.get(i) <= price) ++ans;
            else break;
        }
        return ans;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

时间：1130ms 击败 6.62%使用 Java 的用户

内存：51.82MB 击败 85.03%使用 Java 的用户

方法二：单调栈(一)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class StockSpanner {

    Deque<int[]> stack;
    int curDay = -1;

    public StockSpanner() {
        stack = new ArrayDeque<>();
        stack.push(new int[]{-1, Integer.MAX_VALUE}); // 这样无需判断栈为空
    }
    
    public int next(int price) {
        while (price >= stack.peek()[1]) stack.pop();
        int ans = ++curDay - stack.peek()[0];
        stack.push(new int[]{curDay, price});
        return ans;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

时间：20ms 击败 94.81%使用 Java 的用户

内存：51.87MB 击败 79.54%使用 Java 的用户

方法三：单调栈(二)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class StockSpanner {

    Deque<int[]> stack;

    public StockSpanner() {
        stack = new ArrayDeque<>();
    }
    
    public int next(int price) {
        int cnt = 1;
        while (!stack.isEmpty() && price >= stack.peek()[1]) {
            cnt += stack.pop()[0];
        }
        stack.push(new int[]{cnt, price});
        return cnt;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

时间：27ms 击败 50.64%使用 Java 的用户

内存：51.96MB 击败 67.87%使用 Java 的用户