买卖股票的最佳时机

题目要求

给定一个数组 prices，其中 prices[i] 表示第 i 天的某支股票的价格。你的任务是找出在哪一天买入并在未来的某一天卖出能够获得的最大利润。你只能进行一次买入和一次卖出操作。如果无法获得利润，则返回 0。

解题思路

要解决这个问题，我们可以遵循以下步骤：

初始化两个变量，一个用于存储到目前为止的最小股价 minPrice，另一个用于存储到目前为止的最大利润 maxProfit。
遍历 prices 数组，对于每一天的价格 prices[i]：
- 更新 minPrice 为当前价格和 minPrice 中的较小值。
- 计算如果在 minPrice 买入，在当前价格 prices[i] 卖出的利润，即 prices[i] - minPrice。
- 更新 maxProfit 为当前计算出的利润和 maxProfit 中的较大值。
遍历完成后，maxProfit 将包含可能的最大利润。如果 maxProfit 大于 0，则返回该值；否则，返回 0。

这个问题的关键在于找到最低购买点和最高卖出点的组合，但这两个点不需要是数组中的连续元素，只要保证卖出的时间在买入之后即可。通过一次遍历即可找到最佳买卖时机，保证了算法的效率。

Golang 版本

package main

import (
	"fmt"
)

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}

	minPrice := prices[0]
	maxProfit := 0

	for _, price := range prices {
		if price < minPrice {
			minPrice = price
		} else if profit := price - minPrice; profit > maxProfit {
			maxProfit = profit
		}
	}

	return maxProfit
}

func main() {
	prices := []int{7, 1, 5, 3, 6, 4}
	fmt.Println("Maximum profit:", maxProfit(prices))
}

这段代码定义了一个 maxProfit 函数，它接受一个整数数组 prices 作为参数，并返回一个整数，表示可以获得的最大利润。main 函数中给出了一个示例数组，并打印出调用 maxProfit 函数后的结果。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int maxProfit(const std::vector<int>& prices) {
    if (prices.empty()) return 0;

    int minPrice = prices[0];
    int maxProfit = 0;

    for (int price : prices) {
        minPrice = std::min(minPrice, price);
        maxProfit = std::max(maxProfit, price - minPrice);
    }

    return maxProfit;
}

int main() {
    std::vector<int> prices{7, 1, 5, 3, 6, 4};
    std::cout << "Maximum profit: " << maxProfit(prices) << std::endl;
    return 0;
}

这段代码定义了一个 maxProfit 函数，它接受一个整数类型的 std::vector 作为参数，并返回一个整数，表示可以获得的最大利润。main 函数中给出了一个示例数组，并打印出调用 maxProfit 函数后的结果。

Python 版本

def max_profit(prices):
    if not prices:
        return 0

    min_price = prices[0]
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

# Example usage:
prices = [7, 1, 5, 3, 6, 4]
print("Maximum profit:", max_profit(prices))

Java 版本

public class StockProfitCalculator {

    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int minPrice = prices[0];
        int maxProfit = 0;

        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Maximum profit: " + maxProfit(prices));
    }
}

这段代码定义了一个 StockProfitCalculator 类，其中包含一个 maxProfit 静态方法，用于计算并返回给定股票价格数组的最大利润。main 方法提供了一个示例数组，并打印出调用 maxProfit 方法后的结果。

Rust 版本

fn max_profit(prices: Vec<i32>) -> i32 {
    let mut min_price = i32::MAX;
    let mut max_profit = 0;

    for &price in prices.iter() {
        if price < min_price {
            min_price = price;
        } else {
            max_profit = max_profit.max(price - min_price);
        }
    }

    max_profit
}

fn main() {
    let prices = vec![7, 1, 5, 3, 6, 4];
    println!("Maximum profit: {}", max_profit(prices));
}

这段代码定义了一个 max_profit 函数，它接受一个 Vec<i32> 类型的参数 prices，并返回一个 i32 类型的值，表示可以获得的最大利润。main 函数中给出了一个示例向量，并打印出调用 max_profit 函数后的结果。

总结

上述问题的解法遵循一个简单的逻辑：在遍历数组的过程中，记录并更新到目前为止遇到的最低价格和最大利润。具体步骤如下：

初始化两个变量：min_price 为最大可能的股票价格，max_profit 为 0。
遍历价格数组 prices：
- 对于每个价格 price，如果 price 小于 min_price，则更新 min_price 为当前 price。
- 否则，计算当前 price 与 min_price 之差，即当前可能的利润，并更新 max_profit 为当前可能利润和 max_profit 中的较大值。
遍历完成后，max_profit 将包含可能的最大利润。

这种方法的关键在于，它只需要一次遍历（时间复杂度为 O(n)），无需使用嵌套循环，因此效率较高。在不同的编程语言中，这个算法的实现思路是一致的，只是语法和一些函数的使用有所不同。

hot-100