LeetCode 问题：买卖股票的最佳时机

我最近解决了一个经典的 LeetCode 问题：“买卖股票的最佳时机”。这道题要求你求出一次买卖股票所能获得的最大利润。让我们深入探讨我探索过的不同方法及其复杂性。这是问题的 URL：

LeetCode 121

蛮力方法（时间复杂度：O(n^2)）

最直接的解决方案可能是将数组中的每个元素与所有剩余元素进行比较。对于每个价格，我们计算如果在稍后的一天出售它会产生的利润。然后我们跟踪遇到的最大利润。然而，这种方法的时间复杂度较高，导致 Time Limit Exceeded。

/**
 * @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 出现“Time Limit Exceeded”错误。

二指针方法（时间复杂度：O(n)）

为了提高效率，我们可以利用先买后卖的事实。我们可以引入两个指针：

• 购买：指向当前的潜在购买价格。
• sell：指向候选售价。

这个想法是从第三个元素开始迭代价格数组（因为前两个元素用于买卖）。我们不断检查卖出价（当前元素）和买入价之间的差额是否大于当前最大利润。如果为真，我们更新最大利润。否则，我们将买入指针更新为当前元素（可能是较低的买入价格）并将卖出指针向前移动一步。

这种方法显着提高了时间复杂度，达到了 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>
  
  
  贪婪方法（时间复杂度：O(n)）与 Python 示例
</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中文网其他相关文章！