前往
大廳
主題

LeetCode - 2110. Number of Smooth Descent Periods of a Stock 解題心得

Not In My Back Yard | 2022-06-12 12:00:04 | 巴幣 0 | 人氣 134

題目連結:


題目意譯:
你被給定一整數陣列 prices 代表著一檔股票每日價格之歷史記錄,其中 prices[i] 為第 i 天時該股票的價格。

一檔股票的一個平滑下降時段為一個或好幾個連續的天數,使得這當中的每一天的價格都比前一天低恰好 1 單位值。時段中的第一天則排除於這個規則之外。

回傳平滑下降時段之數量。

限制:
1 ≦ prices.length ≦ 10 ^ 5
1 ≦ prices[i] ≦ 10 ^ 5



範例測資:
範例 1:
輸入: prices = [3,2,1,4]
輸出: 7
解釋: 有七個平滑下降時段:
[3] 、 [2] 、 [1] 、 [4] 、 [3,2] 、 [2,1] 和 [3,2,1]
注意到,根據定義只包含一天的時段也算作一個平滑下降時段。

範例 2:
輸入: prices = [8,6,7,7]
輸出: 4
解釋: 有四個平滑下降時段:[8] 、 [6] 、 [7] 和 [7]
注意到 [8, 6] 不是一個平滑下降時段,因為 8 - 6 ≠ 1。

範例 3:
輸入: prices = [1]
輸出: 1
解釋: 有一個平滑下降時段:[1]


解題思維:
可以看到一個長度為 L 平滑下降時段,其蘊含了
L 個長度 1 的時段、
L - 1 個長度 2 的時段、
L - 2 個長度 3 的時段、
……
2 個長度 L - 1 的時段、
1 個長度 L 的時段(即本身),
總計 (L + 1) × L ÷ 2 個時段。

而由於時段是連續的。因此我們可以掃過一次 prices 便可以將其分成若干個盡可能地大的平滑下降時段,也就是每個時段不會再被包進一個更大的時段中。判斷方式很簡單,當目前看到的價格 prices[i] 如果不是前一天的價格 prices[i - 1] 減 1 的話,則我們便可以看到 prices[i] 與 prices[i - 1] 是位於不同的時段,即 prices[i] 為一個時段之開頭。

最後把所有時段各自蘊含的時段數量全部加總起來即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作