題目： LeetCode - 901. Online Stock Span

題目說明

設計一個 Class，負責收集每日股票的價格及跨度 ( 從今天開始往前數前面有幾天比今天的價格低 )。

解題思路

解法一： 動態規劃，dp[i] 代表第 i 天時前面有連續幾天比今天的價格低。當每次呼叫 next() 時，j = i - 1 表示前一天的價格，若是 prices[i - 1] <= price，就將 j 減去 dp[j]，表示前面有多少天的價格小於今天的價格，重複執行直到 j < 0 或是 price < prices[j]，最後 i - j + 1 即是今天價格的跨度，最後將跨度推入 dp 及價格推入 prices 即可。

解法二： 解法二其實是解法一的濃縮，我們可以發現，當 dp[i] 的數值確定後，前面幾天的資料其實就不需要了，所以我們可以使用 Stack，當每次呼叫 next() 時，若是 top() 的價格小於等於今天的價格，就將跨度加到今天，然後 pop() 掉，最後再將今天的價格及跨度推入即可。

參考解法

解法一：

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
26
27
28
29
30
31
32
33
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class StockSpanner {
public:
    StockSpanner() {
        i = 0;
    }
    
    int next(int price) {
        if(i == 0 || price < prices.back())
            dp.push_back(1);
        else
        {
            int j = i - 1;
            while(j >= 0 && price >= prices[j])
                j -= dp[j];
            dp.push_back(i - j);
        }
        ++i;
        prices.push_back(price);
        return dp.back();
    }
private:
    vector<int> dp;
    vector<int> prices;
    int i;
};

解法二：

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
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0; 
}();
class StockSpanner {
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        int span = 1;
        while(!s.empty() && s.top().first <= price)
            span += s.top().second, s.pop();
        s.emplace(price, span);
        return span;
    }
private:
    // {price, span}
    stack<pair<int, int>> s;
};