題目: 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
| 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
| 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: stack<pair<int, int>> s; };
|