买卖股票，我概括了这 3 点经验
发布时间：2021-06-03 15:53:13 所属栏目：大数据 来源：互联网
导读：1. Best Time to Buy and Sell Stock 给你一组数组 prices=[7,1,5,3,6,4]。prices[i] 代表在第i天股票的价格。你可以进行买与卖的操作，但你得先买了才能卖。(也就是不能 short)你最多进行一次买与卖的操作，问你能够赚到的最大收益是多少?从本题的数据例子
|
1. Best Time to Buy and Sell Stock
给你一组数组 prices=[7,1,5,3,6,4]。prices[i] 代表在第i天股票的价格。你可以进行买与卖的操作，但你得先买了才能卖。(也就是不能 short)你最多进行一次买与卖的操作，问你能够赚到的最大收益是多少?从本题的数据例子来看，我们如果在 i=1 天买和在 i=4天卖，我们能够赚到 p[4]-p[1]=5 的收益。这是我们能够做到的最大收益，其它的操作都不能赚的比5多。
问题分析 ：
首先如果我们在第 i 天进行买的操作，那么卖的操作一定得发生在第 i 天之后，也就是 prices[i+1 : n] 里
以 prices=[7,1,5,3,6,4] 作为例子，如果我们在 prices[0] 买，那么卖一定发生在 prices[1 : 5]。
同理，如果我们在 prices[1] 买，卖一定发生在 prices[2 : 5]。
我们可以把所有的 (买，卖) pair 生成出来然后找到收益性最高的那对即可。
方法1 ：暴力枚举
public int maxProfit(int[] prices) {
int maxProfit = 0; //我们可以不进行操作，所以初始是 0 而不是 INT_MIN
for(int i = 0; i < prices.length; i++){
//在 i 天 进行购买
for(int j = i + 1; j < prices.length; j++){
//在 j 天进行出售
int profit = prices[j] - prices[i];
maxProfit = Math.max(maxProfit, profit);
}
}
return maxProfit;
}
代码总结：
我们枚举所有的 (i, j) pair，i 代表买，j 代表卖，并且 i < j，但以上暴力代码的时间复杂度是 O(n^2)，我们可不可以做的更好呢?
时空复杂度：
时间复杂度：O(N^2)
空间复杂度：O(1)
方法2：
如果我们在第 i 天进行买的操作，那么卖的操作一定还是得发生在 prices[i+1 : n] 这个定理是不变的。
换句话说，对于每个买的操作，prices[i]，我们只需要找到 prices[i+1 : n] 里最大的数即可。
我们可以用一个dp array 去记录，dp[i] 表示 max(prices[i : n]) 。
如果我们在 i 这天进行买的操作，获得的最大的收益就是 dp[i+1] - prices[i] (这里我们要注意outbound)
public int maxProfit(int[] prices) {
int maxProfit = 0;
int n = prices.length;
int dp[] = new int[n];
dp[n - 1] = prices[n - 1];
for (int i = n - 2; i >= 0; i--) {
dp[i] = Math.max(prices[i], dp[i + 1]);
}
for (int i = 0; i < n - 1; i++) {
maxProfit = Math.max(maxProfit, dp[i + 1] - prices[i]);
}
return maxProfit;
}
时空复杂度：
时间复杂度：O(N)
空间复杂度：O(N)
 （编辑：威海站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
