LeetCode の問題: 株を売買する最適な時期

私は最近、LeetCode の古典的な問題「株式の売買に最適な時期」に取り組みました。この問題では、株式を 1 回売買することで得られる最大利益を求めるように求められます。私が検討したさまざまなアプローチとその複雑さについて詳しく見ていきましょう。問題の URL は次のとおりです:

リートコード 121

ブルート フォース アプローチ (時間計算量: O(n^2))

最も簡単な解決策は、配列内のすべての要素を残りのすべての要素と比較することかもしれません。各価格について、後日販売した場合に生じる利益を計算します。次に、遭遇した最大利益を追跡します。ただし、このアプローチでは時間の複雑さが高く、制限時間の超過が発生します。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {

    let max = 0;
    for (var i = 0; i  a) return b - a;
    else return 0;
}

その理由は次のとおりです: 各要素を他の n-1 個の要素と比較すると、n*(n-1)/2 の比較が行われます。これはおおよそ O(n^2) の時間計算量に相当し、大規模なデータセットでは非効率的になります。残念ながら、このアプローチでは、LeetCode で「制限時間を超過しました」エラーが発生することがよくあります。

2 ポインター手法 (時間計算量: O(n))

効率を向上させるために、販売する前に購入しているという事実を活用できます。 2 つのポインタを紹介します:

• buy: 現在の潜在的な購入価格を指します。
• sell: 売値候補を指します。

考え方は、3 番目の要素から始めて、prices 配列を反復処理することです (最初の 2 つの要素は売買に使用されるため)。売値（現在の要素）と買値の差が現在の最大利益よりも大きいかどうかを継続的にチェックします。 true の場合、最大利益を更新します。それ以外の場合は、買いポインタを現在の要素 (潜在的にはより低い購入価格) に更新し、売りポインタを 1 ステップ前に移動します。

このアプローチでは、時間の計算量が大幅に改善され、配列を 1 回繰り返すだけで O(n) に達します。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let maxProfit = 0;
    let buy = 0;
    let sell = 1;
    while (sell 



<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172284027594031.png?x-oss-process=image/resize,p_40" class="lazy" alt="LeetCode の問題: 株を売買する最適な時期" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<h2>
  
  
  Python を使用した貪欲なアプローチ (時間計算量: O(n)) の例
</h2>

<p>貪欲なアプローチを使用すれば、同様の時間計算量を達成できます。ここで重要なのは、安く買って高く売った場合にのみ最大の利益を達成できることを理解することです。  したがって、価格配列を反復処理して、これまでに発生した最低価格を追跡できます。これは潜在的な購入価格を表します。</p>

<p>これは貪欲なアプローチの Python 実装です:<br>
</p>

<pre class="brush:php;toolbar:false">class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0;
        min_buy = float('inf')
        for price in prices:
            min_buy = min(min_buy , price )
            max_profit =  max(max_profit, price-min_buy)
        return max_profit

私のポートフォリオの他の場所については、いつでもここで確認できます

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