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

Question

这是我的 leetcode 问题代码 - Best Time to Buy and Sell Stock 3 我的 Golang 代码通过了 203/214 测试用例。对于大小为 10k 的特定输入数组，超出了我的时间限制。有任何想法吗？

基本算法如下：-

1. 找到价格下降的指数，并忽略它之前的所有元素。例如，如果一个数组像 [5,4,3,2,1,2,3,4]，这里的价格一直下降到第 4 个索引。

2. 找到所有局部最小值和局部最大值。因为除非是局部最小值，否则您不想购买

3. 如果只有一项有利可图的交易，即只有一项局部最小值和一项局部最大值，则将其返回。

4. 通过检查以局部最小值买入和以局部最大值卖出的所有排列，找到所有有利可图的交易对。

5. 返回最高交易对

我的代码：

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 {&nbsp; &nbsp; if v1 < v2 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return v1&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return v2&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;func getMax(v1 int, v2 int) int {&nbsp; &nbsp; if v1 > v2 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return v1&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return v2&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;func maxProfit(prices []int) int {&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; var cp1, cp2, mp1, mp2 int&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; cp1 = math.MaxInt&nbsp; &nbsp; cp2 = math.MaxInt&nbsp; &nbsp; mp1 = 0&nbsp;&nbsp; &nbsp; mp2 = 0&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; for i:= 0; i < len(prices); i++ {&nbsp; &nbsp; &nbsp; &nbsp; cp1 = getMin(cp1, prices[i])&nbsp; &nbsp; &nbsp; &nbsp; mp1 = getMax(mp1, prices[i]-cp1)&nbsp; &nbsp; &nbsp; &nbsp; cp2 = getMin(cp2, prices[i]-mp1)&nbsp; &nbsp; &nbsp; &nbsp; mp2 = getMax(mp2, prices[i]-cp2)&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; 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 美元，两者意思相同）