901. Online Stock Span

Version #2 Binary Search
Time O(logn)

class StockSpanner {
    // int[0] -> the minimum stock price needed to connect to current range
    // int[1] -> the length of current range
    // int[2] -> index of the first price in current range
    List<int[]> minRange;
    int lastIndex;
    int count;
 
    public StockSpanner() {
        this.minRange = new ArrayList<>();
        this.lastIndex = -1;
        this.count = 0;
    }
 
    public int next(int price) {
        int start = 0;
        int end = lastIndex;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (minRange.get(mid)[0] > price) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        int result = 0;
        if (minRange.size() == 0 || minRange.get(start)[0] > price) {
            result = 1;
            insert(lastIndex + 1, new int[]{price, result, count});
        } else {
            result = count - minRange.get(start)[2] + 1;
            insert(start, new int[]{price, result, minRange.get(start)[2]});
        }
        count++;
        return result;
    }
 
    private void insert(int index, int[] value) {
        if (index == minRange.size()) {
            minRange.add(value);
        } else {
            minRange.get(index)[0] = value[0];
            minRange.get(index)[1] = value[1];
            minRange.get(index)[2] = value[2];
        }
        lastIndex = index;
    }
}

Version #1 Stack
Time Worstcase O(n)
SpaceO (n)

class StockSpanner {
    Stack<int[]> stack;

    public StockSpanner() {
        this.stack = new Stack<>();
    }

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