【牛客刷题-算法】NC7 买卖股票的最好时机(一)

个人主页：清风莫追
系列专栏：牛客刷题——数据结构与算法

---

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

4.运行结果

成功通过！

---

感谢阅读

个人主页：清风莫追

CSDN话题挑战赛第2期
参赛话题：学习笔记