运行时间超出买卖股票的最佳时间 3

Question

这是我的 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                    }                    

Answer 1

您是否考虑过这样一个事实，即您的方法很好但对于 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 美元，两者意思相同）