1.题目描述
描述
假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
如果不能获取到任何利润，请返回0
假设买入卖出均无手续费
数据范围： 0 ≤ n ≤ 1 0 5 , 0 ≤ v a l ≤ 1 0 4 0 \le n \le 10^5 , 0 \le val \le 10^40≤n≤10
5
,0≤val≤10
4
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
2.算法设计思路
一种比较暴力的想法，因为一共只能进行一次买入和卖出，所以只要求每一天与后面所有天数股价的差值，然后从中找出差值（后面的股价 - 前面的股价）最大组合即可。这样的时间复杂度将达到o ( n 2 ) o(n^2)o(n
2
)。
这里介绍另一种更加简单的方法。我们可以在一次遍历股票价格的过程中，动态地维护一个记录往日最低股价的变量，并与当日的股价相比较，则得到当日卖出股票能拿到的最大利润。
举个例子，对于输入的股价序列[8,9,2,5,4,7,1]，我们可以在遍历的过程中，像下面的表格一样从左往右地更新数据。这样的时间复杂度将为o ( n ) o(n)o(n)，空间复杂度为o ( 1 ) o(1)o(1)。
天数 1 2 3 4 5 6 7
今日股价 8 9 2 5 4 7 1
今日以前最低股价 无 8 8 2 2 2 2
今日卖出最高利润 无 1 -6 3 2 5 -1
历史最大利润（含今日） 无 1 1 3 3 5 5
3.代码实现
注：这里并不是完整代码，而只是核心代码的模式 /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @param pricesLen int prices数组长度 * @return int整型 */ #define big 987654321 //第一天以前的往期最低股价不存在，将其表示为无穷大 int maxProfit(int* prices, int pricesLen ) { // write code here int min = big; //维持往期最低股价 int max = 0; //维持截至今日的最高利润 int t = 0; //当天的最大化利润 for(int i = 0; i < pricesLen; i++){ t = prices[i] - min; if(t > max){ max = t; } if(prices[i] < min){ min = prices[i]; } } return max; }
4.运行结果
成功通过！
