力扣第122题：买卖股票的最佳时机 II

力扣第122题：买卖股票的最佳时机 II - C语言解法

题目描述

给定一个数组 prices，其中 prices[i] 是一支股票第 i 天的价格。你可以多次买入和卖出股票，求能够获得的最大利润。

注意：

• 你不能同时参与多笔交易（即必须在再次买入前出售掉之前的股票）。
• 在任何一天，你都可以选择不进行任何操作。

示例 1：

输入：[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：

输入：[1,2,3,4,5]
输出：4
解释：在第1天（股票价格 = 1）买入，在第5天（股票价格 = 5）卖出，最大利润 = 5 - 1 = 4。

示例 3：

输入：[7,6,4,3,1]
输出：0
解释：在这种情况下, 不进行交易也可以获得最大利润，返回 0。

解题思路

1. 贪心算法

在这道题中，我们允许在多天进行买卖操作，因此我们可以采用 贪心算法 来解决问题。关键是要捕捉到所有能够获得利润的买卖机会。

交易规则

• 如果当前股价比昨天的股价高，我们就可以在昨天买入，在今天卖出。也就是说，当前股价大于前一天的股价时，就进行卖出交易，累积利润。
• 反之，如果今天的股价比昨天低，则我们不进行任何交易。

解题思路

1. 我们遍历整个股价数组，对于每一天的价格，如果今天的价格高于昨天的价格，那么就进行交易（即把利润加上今天的价格和昨天的价格的差）。
2. 最终累积的利润就是最大利润。

2. 时间复杂度

• 时间复杂度：$O(n)$，我们只需要遍历一次股价数组，其中 $n$ 是股票价格数组的长度。
• 空间复杂度：$O(1)$，我们只需要常数空间来存储当前的利润。

C语言代码实现

#include <stdio.h>
#include <stdlib.h>

int maxProfit(int* prices, int pricesSize) {
    if (pricesSize == 0) return 0;  // 如果没有价格，最大利润为 0

    int max_profit = 0;

    // 遍历价格数组，找出所有的买入卖出机会
    for (int i = 1; i < pricesSize; i++) {
        // 如果今天的价格比昨天的价格高，就进行交易（卖出）
        if (prices[i] > prices[i - 1]) {
            max_profit += prices[i] - prices[i - 1];
        }
    }

    return max_profit;
}

int main() {
    // 示例1
    int prices1[] = {7, 1, 5, 3, 6, 4};
    int size1 = sizeof(prices1) / sizeof(prices1[0]);
    printf("最大利润：%d\n", maxProfit(prices1, size1));  // 输出：7

    // 示例2
    int prices2[] = {1, 2, 3, 4, 5};
    int size2 = sizeof(prices2) / sizeof(prices2[0]);
    printf("最大利润：%d\n", maxProfit(prices2, size2));  // 输出：4

    // 示例3
    int prices3[] = {7, 6, 4, 3, 1};
    int size3 = sizeof(prices3) / sizeof(prices3[0]);
    printf("最大利润：%d\n", maxProfit(prices3, size3));  // 输出：0

    return 0;
}

代码解析

1. maxProfit 函数

int maxProfit(int* prices, int pricesSize) {
    if (pricesSize == 0) return 0;  // 如果没有价格，最大利润为 0

    int max_profit = 0;

    // 遍历价格数组，找出所有的买入卖出机会
    for (int i = 1; i < pricesSize; i++) {
        // 如果今天的价格比昨天的价格高，就进行交易（卖出）
        if (prices[i] > prices[i - 1]) {
            max_profit += prices[i] - prices[i - 1];
        }
    }

    return max_profit;
}

• maxProfit：该函数通过遍历股价数组，找出所有的买入卖出机会。如果今天的股价比昨天的股价高，则认为今天是一个卖出的时机，并将差价加入 max_profit 中。最后返回最大利润。

• 贪心算法：我们每次遇到价格上升的情况，就进行交易。这样确保我们最大化每次的利润。

2. main 函数

int main() {
    // 示例1
    int prices1[] = {7, 1, 5, 3, 6, 4};
    int size1 = sizeof(prices1) / sizeof(prices1[0]);
    printf("最大利润：%d\n", maxProfit(prices1, size1));  // 输出：7

    // 示例2
    int prices2[] = {1, 2, 3, 4, 5};
    int size2 = sizeof(prices2) / sizeof(prices2[0]);
    printf("最大利润：%d\n", maxProfit(prices2, size2));  // 输出：4

    // 示例3
    int prices3[] = {7, 6, 4, 3, 1};
    int size3 = sizeof(prices3) / sizeof(prices3[0]);
    printf("最大利润：%d\n", maxProfit(prices3, size3));  // 输出：0

    return 0;
}

• 输入数据：我们提供了三个示例，分别对应不同的股价数组。
• 输出结果：通过调用 maxProfit 函数，我们计算并打印出最大利润。

示例输出

最大利润：7
最大利润：4
最大利润：0

总结

本题的解法采用了 贪心算法，通过遍历股价数组，找出所有能够获得利润的买卖机会。每当股价上涨时，我们就进行卖出，并累积利润。最终，我们得到了最大利润。时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，是一个高效的解法。