###### tags: `Leetcode` `medium` `design` `stack` `python` `c++`

# 901. Online Stock Span

## [題目連結:] https://leetcode.com/problems/online-stock-span/

## 題目:
Design an algorithm that 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 in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

* For example, if the prices of the stock in the last four days is ```[7,2,1,2]``` and the price of the stock today is ```2```, then the span of today is ```4``` because starting from today, the price of the stock was less than or equal ```2``` for ```4``` consecutive days.
* Also, if the prices of the stock in the last four days is ```[7,34,1,2]``` and the price of the stock today is ```8```, then the span of today is ```3``` because starting from today, the price of the stock was less than or equal ```8``` for ```3``` consecutive days.

Implement the ```StockSpanner``` class:

* ```StockSpanner()``` Initializes the object of the class.
* ```int next(int price)``` Returns the **span** of the stock's price given that today's price is price.

**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
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80);  // return 1
stockSpanner.next(60);  // return 1
stockSpanner.next(70);  // return 2
stockSpanner.next(60);  // return 1
stockSpanner.next(75);  // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85);  // return 6

## 解題想法:
* 此題為，實作next函式:
* 每次給當天股價
* 返回**之前連續多少天是小於等於**當天的股價
* (從今天向前面數已經經過的天數，今天也包括在内)

* 想法:
* 對於"連續": 只需往前找到第一個比當前數字大的位置即可
* ex: 對於目前數字10,前面有x個數字比他小or相等
* 當後面出是:
* 15: 比10大,則前面小於15的各數即為x+1
* 8: 比10小,則前面小於8的各數即為1
* 使用stack:
* 其中存的數為遞減(大->小)
* 對於當前數，每次比對stack[-1]

## Python:

class StockSpanner(object):

    def __init__(self):
        self.stack=[]
        #每次存(當前數字,當前小於等於該數的各數)

    def next(self, price):
        """
        :type price: int
        :rtype: int
        """
        res=1
        while self.stack and self.stack[-1][0]<=price:
            res+=self.stack.pop()[1]
        self.stack.append((price,res))
        return res


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

## C++:

class StockSpanner {
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        int res=1;
        while (!tmp.empty() && tmp.top().first<=price){
            res+=tmp.top().second; tmp.pop();
        }
        pair<int, int> cur(price,res);
        tmp.push(cur);
        return res;
    }

private:
    stack<pair<int,int>> tmp;
};

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