#P4029. 买卖股票的最佳时机
-
ID: 2245
Tried: 107
Accepted: 51
Difficulty: 3
-
算法标签>贪心
买卖股票的最佳时机
题目内容
给定一个数组 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<=105
- 0<=prices[i]<=104
题解
题面描述
给定一个数组 prices，其中第 i 个元素 prices[i] 表示一支股票在第 i 天的价格。要求在某一天买入并在未来的某一天卖出，使得获得的利润最大。若不存在任何利润，则返回 0。
思路
遍历数组时，维护两个变量：
- minPrice：到当前为止的最小股票价格（表示最佳买入时机）。
- maxProfit：当前能够获得的最大利润，即当前价格与 minPrice 的差值的最大值。
算法步骤：
- 初始时将 minPrice 设为一个足够大的值，maxProfit 设为 0。
- 对于每一天的价格 prices[i]：
- 更新 minPrice=min(minPrice,prices[i])。
- 更新 maxProfit=max(maxProfit,prices[i]−minPrice)。
- 最终返回 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;
}
}