LeetCode の解読。株式を売買するのに最適な時期 II

LeetCode のスキルを磨くという継続的な探求の中で、私は「株式の売買に最適な時期 II」の問題に取り組みました。この課題は、古典的な「株式の売買に最適な時期 II」問題 (LeetCode 121) のフォローアップですが、決定的な違いがあります: *利益を最大化するために複数のトランザクションを実行できます。
*

視覚的なアプローチ

コードに取り組む前に、ホワイトボード上で問題を視覚化することが非常に役立つことがわかりました。これにより、問題をより小さく、より管理しやすいステップに分割することができました。

貪欲なアプローチ

無制限のトランザクションを実行できる柔軟性を考慮すると、貪欲なアプローチは有望であるように思えました。中心となる考え方はシンプルです。株価が前日と比較して上昇するたびに、それは潜在的な利益の機会であると考えられます。これらすべての価格差を合計することで、最大利益が効率的に計算されます。

Pythonの実装

この貪欲な戦略を実装する Python コードは次のとおりです。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                profit+=prices[i] - prices[i-1]

        return profit

JavaScriptの実装

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var profit = 0;
    for (var i = 1; i < prices.length; i++)
    {
    if(prices[i] > prices[i-1])
    {
        profit += Number(prices[i] - prices[i-1])
    }
    }

    return profit
};

時間と空間の複雑さ

• このアプローチの時間計算量は O(N) です (N = 配列の長さ)。
• その場で比較しているため、空間複雑度は N(1) です。

以上がLeetCode の解読。株式を売買するのに最適な時期 IIの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。