CSDN 个人主页：清风莫追

系列专栏：牛客刷题——数据结构与算法推荐一款面试、刷题神器牛客网：👉点击开始刷题学习👈

@[toc]

1.题目描述

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

1. 你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2. 如果不能获取到任何利润，请返回 0

3. 假设买入卖出均无手续费

数据范围： $0\le n\le 10^5,0\le val\le 10^4$要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

注：图片来自牛客网

2.算法设计思路

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

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

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

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.运行结果

成功通过！

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读

个人主页：清风莫追