代码训练LeetCode(15)买卖股票

代码训练(15)LeetCode之买卖股票

Author: Once Day Date: 2024年4月22日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

122. 买卖股票的最佳时机 II - 力扣（LeetCode）
力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

- - 代码训练(15)LeetCode之买卖股票

1. 原题

例如对于prices = [7,1,5,3,6,4]，最大利润为7，即：

在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

2. 分析

这道题需要找出在给定股票价格数组 prices 中能获得的最大利润，其中 prices[i] 代表第 i 天的股票价格。规则是在任何一天，可以决定是否购买或者出售股票，但最多只能持有一股股票，并且允许在同一天买入和卖出。题目要求返回可能的最大利润。

关键在于理解在哪些天买入和在哪些天卖出可以获得最大利润。由于可以在同一天买入和卖出，那么只要今天的价格比昨天高，就可以认为昨天买入，今天卖出是有利可图的。

具体策略是：

遍历价格数组，从第二天开始比较。
每当发现今天的价格比昨天的高，就计算这一天的利润（今天的价格减去昨天的价格），并累加到总利润中。

这种策略的好处在于不需要维护任何复杂的状态，只需要在价格上升的时候“买卖”即可。

分析步骤：

初始化一个变量 maxProfit 来存储总利润，初值设为0。
从第二天开始遍历价格数组。
对于每一天，如果价格比前一天高，就将差价加到 maxProfit 上。
最后返回 maxProfit。

性能优化关键点：

执行速度：这个算法的时间复杂度是 O(n)，因为只需要遍历一次价格数组，这是非常高效的。
内存使用：空间复杂度为 O(1)，因为我们只使用了常数额外空间。

3. 代码实现

int maxProfit(int* prices, int pricesSize) {
    int32_t i, state, money, buy_price, last_price;

    state = 1; /* 买入 */
    money = 0;
    last_price = buy_price = prices[0];
    for (i = 1; i < pricesSize; i++) {
        if (prices[i] < last_price) {
            /* 降价卖出 */
            if (state) {
                money += last_price - buy_price;
                state = 0;
            }
        } else if (prices[i] > last_price) {
            /* 升价买入 */
            if (!state) {
                buy_price = last_price;
                state = 1;
            }
        }
        last_price = prices[i];
    }

    /* 最后直接卖掉 */
    if (state) {
        money += last_price - buy_price;
    }

    return money;
}

这段代码实现了一个简单的股票交易策略，目标是最大化利润。函数的输入是一个整数数组 prices，表示一段时间内股票的价格变化，数组的大小为 pricesSize。

代码的主要逻辑如下：

初始化变量：state 表示当前的交易状态，1 表示持有股票（买入），0 表示不持有股票（卖出），money 表示当前的总利润，

buy_price 表示最近一次买入的价格，last_price 表示上一次的股票价格。
遍历价格数组，从下标 1 开始：
- 如果当前价格小于上一次的价格（降价）：
  - 如果当前持有股票（state 为 1），则卖出股票，计算利润并更新 money，将 state 设为 0。
- 如果当前价格大于上一次的价格（升价）：
  - 如果当前不持有股票（state 为 0），则买入股票，将 buy_price 设为上一次的价格，将 state 设为 1。
- 更新 last_price 为当前价格。
遍历结束后，如果仍持有股票（state 为 1），则以最后一个价格卖出，计算利润并更新 money。
返回总利润 money。

这个策略的核心思想是：在价格下降时卖出，在价格上升时买入，以期获得最大利润。

运行结果如下所示(仅供参考):

代码训练LeetCode(15)买卖股票-LMLPHP

4. 总结

这个问题考察了对数组遍历和简单逻辑判断的应用，以及如何从实际问题中抽象出有效的解决方案。通过这种问题，可以加强对简单贪心算法的理解和应用。

Once_day