1.题目描述

描述
假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
如果不能获取到任何利润，请返回0
假设买入卖出均无手续费

数据范围：

≤

0 \le n \le 10^5 , 0 \le val \le 10^4

$0 \leq n \leq 1 0^{5}, 0 \leq v a l \leq 1 0^{4}$
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

注：图片来自牛客网

2.算法设计思路

一种比较暴力的想法，因为一共只能进行一次买入和卖出，所以只要求每一天与后面所有天数股价的差值，然后从中找出差值（后面的股价 – 前面的股价）最大组合即可。这样的时间复杂度将达到

(

)

o(n^2)

$o (n^{2})$ 。

这里介绍另一种更加简单的方法。我们可以在一次遍历股票价格的过程中，动态地维护一个记录往日最低股价的变量，并与当日的股价相比较，则得到当日卖出股票能拿到的最大利润。

举个例子，对于输入的股价序列[8,9,2,5,4,7,1]，我们可以在遍历的过程中，像下面的表格一样从左往右地更新数据。这样的时间复杂度将为

(

)

o(n)

$o (n)$ ，空间复杂度为

(

)

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;
}