Leetcode ―トップインタビュー―。株を売買するのに最適な時期

次のような簡単な問題です。

価格の配列が与えられます。ここで、prices[i] は i 日目の特定の株式の価格です。

ある株を買う日を選択し、その株を売るために将来の別の日を選択することで、利益を最大化したいと考えています。
この取引から達成できる最大の利益を返します。利益を達成できない場合は、0 を返します。

例 1:

入力: 価格 = [7,1,5,3,6,4]
出力: 5

説明: 2 日目に買い (価格 = 1)、5 日目に売る (価格 = 6)、利益 = 6-1 = 5。
販売する前に購入する必要があるため、2 日目に買って 1 日目に売ることはできないことに注意してください。

例 2:

入力: 価格 = [7,6,4,3,1]
出力: 0

説明: この場合、取引は行われず、最大利益 = 0.

制約:

1 0

最初は並べ替えて、より小さい数値とより大きな数値を取得することを考えるでしょうが、配列から前後で異なる範囲や数値を取得する可能性があり、その違いが期待されるものと一致しない可能性があるため、並べ替えのことは忘れてください。

この場合を解決する良い方法は、配列を反復しながら最小値と最大値、およびその差を考慮することです。最小値が予想より小さい場合は、すべてをリセットします。そうでない場合は、続行して最大値より小さい場合は最大値を更新し、最大値だけでなく常に差分を取得します。そうしないと、最小値が小さくても大きな最大値が得られない場合に失敗する可能性があります。 .

class Solution {
    public int maxProfit(int[] prices) {

        int min = prices[0];
        int max = prices[0];
        int diff = 0;

        for(int i=1;i<prices.length;i++) {
            if(min > prices[i]){
                min = prices[i];
                max = prices[i];
            } else if (max < prices[i]) {
                max = prices[i];
            }

            if(diff < (max - min)) {
                diff = max - min;
            }
        }

        return diff;
    }
}

実行時間: 2 ミリ秒。株式の売買に最適な時間に関する Java オンライン送信の 77.66% よりも高速です。

メモリ使用量: 61.4 MB、株式の売買に最適な時期に対する Java オンライン送信の 80.34% 未満。

min を削除して max のみを使用するとさらに改善できますが、その違いは大したことではありませんが、それでもパフォーマンスは向上します。

—

それだけです！他に議論したいことがあれば、お気軽にコメントしてください。何か見逃した場合はお知らせください。適宜更新します。

次の投稿まで！ :)

以上がLeetcode ―トップインタビュー―。株を売買するのに最適な時期の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。