LeetCode 901 - Online Stock Span

https://leetcode.com/problems/online-stock-span/

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Clearly, we need to focus on how to make each query faster than a linear scan. In a typical case, we get a new element like 7, and there are some previous elements like 11, 3, 9, 5, 6, 4. Let's try to create some relationship between this query and the next query.

If (after getting 7) we get an element like 2, then the answer is 1. So in general, whenever we get a smaller element, the answer is 1.

If we get an element like 8, the answer is 1 plus the previous answer (for 7), as the 8 "stops" on the same value that 7 does (namely, 9).

If we get an element like 10, the answer is 1 plus the previous answer, plus the answer for 9.

Notice throughout this evaluation, we only care about elements that occur in increasing order - we "shortcut" to them. That is, from adding an element like 10, we cut to 7 [with "weight" 4], then to 9 [with weight 2], then cut to 11 [with weight 1].

A stack is the ideal data structure to maintain what we care about efficiently.

Algorithm

Let's maintain a weighted stack of decreasing elements. The size of the weight will be the total number of elements skipped. For example, 11, 3, 9, 5, 6, 4, 7 will be (11, weight=1), (9, weight=2), (7, weight=4).

When we get a new element like 10, this helps us count the previous values faster by popping weighted elements off the stack. The new stack at the end will look like (11, weight=1), (10, weight=7).

https://leetcode.com/articles/online-stock-span/

class StockSpanner {

    Stack<Integer> prices, weights;

    public StockSpanner() {

        prices = new Stack();

        weights = new Stack();

    }

    public int next(int price) {

        int w = 1;

        while (!prices.isEmpty() && prices.peek() <= price) {

            prices.pop();

            w += weights.pop();

        }

        prices.push(price);

        weights.push(w);

        return w;

    }

}

https://leetcode.com/problems/online-stock-span/discuss/168311/C%2B%2BJavaPython-O(1)

Push every pair of <price, result> to a stack.
Pop lower price from the stack and accumulate the count.

One price will be pushed once and popped once.
So 2 * N times stack operations and N times calls.

@Sithis suggest some similar problems to practice monotone stack:

496. Next Greater Element I
497. Next Greater Element II
498. Daily Temperatures
499. Sum of Subarray Minimums
500. Largest Rectangle in Histogram

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

https://leetcode.com/problems/online-stock-span/discuss/168308/Short-Java-Solution

        Stack<Item> s = new Stack<>();

        public int next(int price) {
            int lessOrEqual = 1;
            while (!s.isEmpty() && s.peek().price <= price)
                lessOrEqual += s.pop().lessOrEqual;
            s.push(new Item(lessOrEqual, price));
            return s.peek().lessOrEqual;
        }

        class Item {
            final int lessOrEqual, price;

            Item(int lessCount, int val) {
                this.lessOrEqual = lessCount;
                this.price = val;
            }
        }

Time Complexity: $O(Q)$, where $Q$ is the number of calls to StockSpanner.next. In total, there are $Q$pushes to the stack, and at most $Q$ pops.

    Stack<Integer> prices, weights;

    public StockSpanner() {

        prices = new Stack();

        weights = new Stack();

    }

    public int next(int price) {

        int w = 1;

        while (!prices.isEmpty() && prices.peek() <= price) {

            prices.pop();

            w += weights.pop();

        }

        prices.push(price);

        weights.push(w);

        return w;

    }

X. https://leetcode.com/problems/online-stock-span/discuss/168288/Java-short-solution-using-list-with-explanation

The idea is to memorize where is the previous bigger price for each price, here prev[i] is the index of the previous bigger price of list[i]

For example list [100, 80, 60, 70, 60, 75, 85] we know the bigger one before 75 is list[1] = 80, when we get to 85, we don't have to search all the way through 75 to 80.

    private List<Integer> list = new ArrayList<>();
    private List<Integer> prev = new ArrayList<>();

    public int next(int price) {
        list.add(price);
        int i = list.size() - 2;
        while (!prev.isEmpty() && i >= 0 && list.get(i) <= price) i = prev.get(i);
        prev.add(i);
        return list.size() - 1 - i;
    }

https://zhanghuimeng.github.io/post/leetcode-901-online-stock-span/

2018.9.16 UPDATE：通过今天的比赛题Leetcode 907，我意识到了一个问题，这个算法比我想象得要更强一些。对于被某个数从栈中弹出的数而言，它右侧第一个比它大的数就是这个数。所以一个方向的一次使用栈的操作可以同时解决两侧的问题。