Masalah LeetCode : Masa Terbaik untuk Membeli dan Menjual Saham

Baru-baru ini saya telah menangani masalah LeetCode klasik: "Masa Terbaik untuk Membeli dan Menjual Saham." Masalah ini meminta anda mencari keuntungan maksimum yang boleh anda perolehi dengan membeli dan menjual saham sekali. Mari kita selami pendekatan berbeza yang saya terokai, bersama dengan kerumitannya. Berikut ialah URL masalahnya:

LeetCode 121

Pendekatan Brute Force (Kerumitan Masa: O(n^2))

Penyelesaian yang paling mudah ialah membandingkan setiap elemen dalam tatasusunan dengan semua elemen yang tinggal. Untuk setiap harga, kami mengira keuntungan yang akan dijana jika dijual pada hari kemudian. Kami kemudian menjejaki keuntungan maksimum yang dihadapi. Pendekatan ini, bagaimanapun, mengalami kerumitan masa yang tinggi dan mengakibatkan Had Masa Melebihi.

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

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

Ini sebabnya: Kami membandingkan setiap elemen dengan n-1 elemen lain, menghasilkan perbandingan n*(n-1)/2. Ini diterjemahkan secara kasar kepada kerumitan masa O(n^2), yang menjadi tidak cekap untuk set data yang besar. Malangnya, pendekatan ini sering membawa kepada ralat "Had Masa Melebihi" pada LeetCode.

Pendekatan Dua Penunjuk (Kerumitan Masa: O(n))

Untuk meningkatkan kecekapan, kami boleh memanfaatkan fakta bahawa kami membeli sebelum menjual. Kami boleh memperkenalkan dua petunjuk:

• beli: Mata kepada potensi harga belian semasa.
• jual: Mata kepada calon harga jualan.

Ideanya adalah untuk mengulangi susunan harga, bermula dari elemen ketiga (memandangkan dua elemen pertama digunakan untuk membeli dan menjual). Kami sentiasa menyemak sama ada perbezaan antara harga jualan (elemen semasa) dan harga beli adalah lebih besar daripada keuntungan maksimum semasa. Jika benar, kami mengemas kini keuntungan maksimum. Jika tidak, kami mengemas kini penunjuk beli kepada elemen semasa (berpotensi harga belian yang lebih rendah) dan menggerakkan penunjuk jualan selangkah ke hadapan.

Pendekatan ini menawarkan peningkatan yang ketara dalam kerumitan masa, mencapai O(n) kerana kami hanya mengulangi tatasusunan sekali sahaja.

/**
 * @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="Masalah LeetCode : Masa Terbaik untuk Membeli dan Menjual Saham" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<h2>
  
  
  Pendekatan Tamak (Kerumitan Masa: O(n)) dengan Contoh Python
</h2>

<p>Kita boleh mencapai kerumitan masa yang sama dengan pendekatan tamak. Perkara utama di sini adalah untuk memahami bahawa keuntungan maksimum hanya boleh dicapai jika kita membeli rendah dan menjual tinggi.  Oleh itu, kita boleh mengulangi tatasusunan harga dan menjejaki harga minimum yang dihadapi setakat ini. Ini mewakili potensi harga belian.</p>

<p>Berikut ialah pelaksanaan Python bagi pendekatan tamak:<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

Anda sentiasa boleh mengetahui lebih lanjut tentang tempat lain untuk mencari saya pada portfolio saya di sini

Atas ialah kandungan terperinci Masalah LeetCode : Masa Terbaik untuk Membeli dan Menjual Saham. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!