901 Online Stock Span

901. Online Stock Span

1. Question

Write a classStockSpannerwhich collects daily price quotes for some stock, and returns thespan 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].

Example 1:

Input: 
["StockSpanner","next","next","next","next","next","next","next"], 
[[],[100],[80],[60],[70],[60],[75],[85]]

Output: [null,1,1,1,2,1,4,6]

Explanation: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.

Note:

1. Calls toStockSpanner.next(int price)will have1 <= price <= 10^5.

2. There will be at most10000calls toStockSpanner.nextper test case.

3. There will be at most150000calls toStockSpanner.nextacross all test cases.

4. The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

2. Implementation

(1) Stack

思路: 题目要求我们给定某一天的股价, 找出在这天(包含这一天)前的所有小于等于当天股价的连续天数，说起来有点拗口，比如题目举得例子中，给定7天的股价为[100, 80, 60, 70, 60, 75, 85], 输出结果为[1, 1, 1, 2, 1, 4, 6]，第六天对应的结果是4，因为第6天的股价是75，在第6天前，比75股价低的连续天数是3，即第3天的60，第4天的70，第5天的60，加上股价为75这一天，总共有4个。

所以做法类似于Leetcode 739, 利用栈。但稍有不同的是，这里的stack存一个pair的数组，数组的第一个元素是price，第二个元素则是小于等于这个price的连续天数，如果stack顶的price小于等于当天的price，则res(初始值为1，因为要包含当天)加上stack.peek()的第二个元素。

class StockSpanner {
    Stack<int[]> stack;

    public StockSpanner() {
        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;
    }
}

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

3. Time & Space Complexity

Stack: 时间复杂度:平均时间是O(1), 最坏情况是O(n), 空间复杂度O(n)