901. Online Stock Span

Violence

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

    private final List<Integer> priceList;

    public StockSpanner() {
        this.priceList = new ArrayList<>();
    }

    public int next(int price) {
        priceList.add(price);

        int i = priceList.size() - 1;
        while (i >= 0 && priceList.get(i) <= price) {
            i--;
        }

        // i == -1 or priceList.get(i) > price
        return priceList.size() - i - 1;
    }

}

Stack

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
class StockSpanner {

    private final Stack<int[]> decreaseStack; // 单调递减栈
    private int index;

    public StockSpanner() {
        this.decreaseStack = new Stack<>();
        this.index = -1;

        decreaseStack.push(new int[]{index, Integer.MAX_VALUE});
    }

    public int next(int price) {
        index++;

        while (decreaseStack.peek()[1] <= price) {
            decreaseStack.pop();
        }

        int peekIndex = decreaseStack.peek()[0]; // 此处保存 peekIndex 是为了防止放入元素后再获取顶端元素时获取到刚放入的元素
        decreaseStack.push(new int[]{index, price});
        return index - peekIndex;
    }

}

References

901. Online Stock Span