题解 | 买卖股票的最好时机(一)
买卖股票的最好时机(一)
https://www.nowcoder.com/practice/351b87e53d0d44928f4de9b6217d36bb
解题思路
要求最大收益，我们需要找到最低的买入价格和在该买入价格之后的最高卖出价格。可以遍历一次数组：
- 用一个变量记录当前遍历过的最低价格
- 用另一个变量记录当前能获得的最大利润
- 对于每个价格，尝试更新最低价格，并计算当前价格卖出能获得的利润
代码
#include <iostream>
#include <vector>
using namespace std;
int maxProfit(vector<int>& prices) {
if(prices.empty()) return 0;
int minPrice = prices[0];
int maxProfit = 0;
for(int i = 1; i < prices.size(); i++) {
maxProfit = max(maxProfit, prices[i] - minPrice);
minPrice = min(minPrice, prices[i]);
}
return maxProfit;
}
int main() {
int n;
cin >> n;
vector<int> prices(n);
for(int i = 0; i < n; i++) {
cin >> prices[i];
}
cout << maxProfit(prices) << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static int maxProfit(int[] prices) {
if(prices.length == 0) return 0;
int minPrice = prices[0];
int maxProfit = 0;
for(int i = 1; i < prices.length; i++) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfit;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] prices = new int[n];
for(int i = 0; i < n; i++) {
prices[i] = sc.nextInt();
}
System.out.println(maxProfit(prices));
sc.close();
}
}
def max_profit(prices):
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
max_profit = max(max_profit, price - min_price)
min_price = min(min_price, price)
return max_profit
n = int(input())
prices = list(map(int, input().split()))
print(max_profit(prices))
算法及复杂度
- 算法：动态规划（一次遍历）
- 时间复杂度：
，其中
为数组长度
- 空间复杂度：
，只使用了常数个变量
海康威视公司氛围 495人发布