题解

题面描述

给定一个数组 $prices$，其中第 $i$ 个元素 $prices[i]$ 表示一支股票在第 $i$ 天的价格。要求在某一天买入并在未来的某一天卖出，使得获得的利润最大。若不存在任何利润，则返回 $0$。

思路

遍历数组时，维护两个变量：

• $minPrice$：到当前为止的最小股票价格（表示最佳买入时机）。
• $maxProfit$：当前能够获得的最大利润，即当前价格与 $minPrice$ 的差值的最大值。

算法步骤：

1. 初始时将 $minPrice$ 设为一个足够大的值，$maxProfit$ 设为 $0$。
2. 对于每一天的价格 $prices[i]$：
   • 更新 $minPrice = \min(minPrice, prices[i])$。
   • 更新 $maxProfit = \max(maxProfit, prices[i] - minPrice)$。
3. 最终返回 $maxProfit$。

这种方法只需遍历一次数组，时间复杂度为 $O(n)$，满足题目要求。

代码分析

• 变量更新：在遍历过程中不断更新 $minPrice$ 和 $maxProfit$，保证在每一天都计算出到目前为止的最大收益。
• 边界情况：当股票价格单调递减时，始终无法获得正利润，因此最终返回 $0$。
• 问题本质：本题实际上是寻找数组中两个数的最大差值，且要求较小的数出现在较大的数之前，这正是一个典型的单次遍历问题。

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// 定义 Solution 类，封装最大利润计算函数
class Solution {
public:
    // 计算最大利润函数
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX; // 初始化最小价格为一个很大的数
        int maxProfit = 0;      // 初始化最大利润为 0
        // 遍历所有价格
        for (int i = 0; i < prices.size(); i++) {
            // 更新到目前为止的最低价格
            minPrice = min(minPrice, prices[i]);
            // 更新最大利润
            maxProfit = max(maxProfit, prices[i] - minPrice);
        }
        return maxProfit;
    }
};

int main(){
    vector<int> prices;
    int price;
    // 读取所有输入数据
    while (cin >> price) {
        prices.push_back(price);
    }
    Solution sol;
    // 输出最大利润
    cout << sol.maxProfit(prices) << endl;
    return 0;
}

Python

# 定义 Solution 类，封装最大利润计算函数
class Solution:
    def maxProfit(self, prices: list) -> int:
        minPrice = float('inf')  # 初始化最小价格为无穷大
        maxProfit = 0            # 初始化最大利润为 0
        # 遍历每一天的股票价格
        for price in prices:
            # 更新到目前为止的最低价格
            minPrice = min(minPrice, price)
            # 更新最大利润
            maxProfit = max(maxProfit, price - minPrice)
        return maxProfit

if __name__ == "__main__":
    import sys
    # 从标准输入读取数据，并将输入的字符串拆分转换为整数列表
    prices = list(map(int, sys.stdin.read().split()))
    sol = Solution()
    # 输出最大利润
    print(sol.maxProfit(prices))

Java

import java.util.Scanner;
import java.util.ArrayList;

// 主类，包含主函数
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        // 从标准输入读取所有整数
        while(sc.hasNextInt()){
            list.add(sc.nextInt());
        }
        int[] prices = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            prices[i] = list.get(i);
        }
        Solution sol = new Solution();
        // 输出最大利润
        System.out.println(sol.maxProfit(prices));
        sc.close();
    }
}

// 定义 Solution 类，封装最大利润计算函数
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE; // 初始化最小价格为最大整数
        int maxProfit = 0;                // 初始化最大利润为 0
        // 遍历每一天的股票价格
        for (int price : prices) {
            // 如果当前价格小于最低价格，则更新最低价格
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                // 如果当前价格与最低价格之差大于当前最大利润，则更新最大利润
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }
}

Leetcode 77.买卖股票的最佳时机-原题链接

题目内容

给定一个数组 $prices$，它的第 $i$ 个元素 $prices[i]$ 表示一支给定股票第 $i$ 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 $0$ 。

输入描述

输入一个数组 $prices$，它的第 $i$ 个元素 $prices[i]$ 表示一支给定股票第 $i$ 天的价格。

输出描述

样例1

输入

7 1 5 3 6 4

输出

5

说明

在第 $2$ 天（股票价格 = $1$）的时候买入，在第$5$ 天（股票价格 =$6$）的时候卖出，最大利润$= 6-1 = 5$ 。

注意利润不能是 $7-1 = 6$, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

样例2

输入

7 6 4 3 1

输出

0

说明

在这种情况下, 没有交易完成, 所以最大利润为 $0$。

提示

• $1 <= prices.length <= 10^5$
• $0 <= prices[i] <= 10^4$