這是我的 leetcode 問題代碼 - Best Time to Buy and Sell Stock 3 我的 Golang 代碼通過了 203/214 測試用例。對于大小為 10k 的特定輸入數組，超出了我的時間限制。有任何想法嗎？基本算法如下：-找到價格下降的指數，并忽略它之前的所有元素。例如，如果一個數組像 [5,4,3,2,1,2,3,4]，這里的價格一直下降到第 4 個索引。找到所有局部最小值和局部最大值。因為除非是局部最小值，否則您不想購買如果只有一項有利可圖的交易，即只有一項局部最小值和一項局部最大值，則將其返回。通過檢查以局部最小值買入和以局部最大值賣出的所有排列，找到所有有利可圖的交易對。返回最高交易對我的代碼：func maxProfit(prices []int) int { //trim left temp, i := 0, 1 for ; i < len(prices) && prices[i] <= prices[temp]; i += 1 { temp = i } if i == len(prices) { return 0 } i -= 1 //find all local lows and highs localLows := []int{i} localHighs := []int{} for j := i + 1; j < len(prices)-1; j += 1 { if prices[j] >= prices[j+1] { for prices[j] == prices[j+1] { j += 1 if j == len(prices)-1 { break } } localHighs = append(localHighs, j) for ; j < len(prices)-1 && prices[j] >= prices[j+1]; j++ { fmt.Print(j, " j") } fmt.Println() localLows = append(localLows, j) } } if prices[len(prices)-1] > prices[len(prices)-2] { localHighs = append(localHighs, len(prices)-1) } fmt.Println(localLows, localHighs) //if only one transaction, return that if len(localHighs) == 1 { return prices[localHighs[0]] - prices[localLows[0]] } //find all profitable transaction pairs maxProfit := 0 for j := 0; j < len(localHighs); j += 1 { for k := j; k < len(localHighs); k += 1 { if prices[localHighs[k]]<prices[localLows[j]]{ continue } transaction1 := int(prices[localHighs[k]] - prices[localLows[j]]) for l := k + 1; l < len(localHighs); l++ { for m := l; m < len(localHighs); m++ { if prices[localHighs[m]]<prices[localLows[l]]{ continue }
1 回答
ITMISS
TA貢獻1871條經驗 獲得超8個贊
您是否考慮過這樣一個事實，即您的方法很好但對于 Leetcode 來說還不夠好？我很難理解狀態機方程式是如何工作的，但在花了很多時間思考之后，我終于明白了。
這是該方法的工作代碼。
func getMin(v1 int, v2 int) int {
if v1 < v2 {
return v1
}
return v2
}
func getMax(v1 int, v2 int) int {
if v1 > v2 {
return v1
}
return v2
}
func maxProfit(prices []int) int {
var cp1, cp2, mp1, mp2 int
cp1 = math.MaxInt
cp2 = math.MaxInt
mp1 = 0
mp2 = 0
for i:= 0; i < len(prices); i++ {
cp1 = getMin(cp1, prices[i])
mp1 = getMax(mp1, prices[i]-cp1)
cp2 = getMin(cp2, prices[i]-mp1)
mp2 = getMax(mp2, prices[i]-cp2)
}
return mp2
}
cp1 是第一筆交易的成本價。mp1 是第一筆交易的最大利潤。
如果此問題僅要求單筆交易的最大利潤，則解決方案到此為止，實際上這是此問題的簡單版本。
由于我們可以選擇執行另一筆交易，盡管該交易與前一筆交易不重疊，因此我們繼續定義 cp2、mp2。
cp2 和 mp2 與 cp1 和 mp1 基本相同，除了 cp2 即成本價 2 或第二筆交易的成本價可能低于給定日期的價格 [i]。
到底為什么少了？這是因為如果我們從第一筆交易中賺取了一些利潤，那么我們可以使用該利潤來抵消或減少第二筆成本價格，這就是我從 cp2 中減去利潤 mp1 的原因。
cp2 = getMin(cp2, prices[i]-mp1)
想一想，如果您今天上午 9 點左右從股票市場的某筆交易中獲利 100 美元，之后什么也沒做，當您在當天晚些時候上午 11 點左右進行第二筆交易以 250 美元的價格購買東西時，您可以說您以 150 美元的價格購買了它（因為當天早些時候您獲利了 100 美元）。這里也是一樣的。如果您最終以 350 美元的價格出售，這意味著您的總利潤為 200 美元（您可以說 350 美元-150 美元或 250 美元-150 美元 +（第一筆交易的 100 美元，兩者意思相同）
- 1 回答
- 0 關注
- 152 瀏覽
添加回答
舉報
0/150
提交
取消