leetcode121：买卖股票的最佳时机

题目链接

leetcode

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    买入并且卖出一次
*/

/*
    贪心算法：实时更新最小值，用当前价格去减最小值来更新最大利润。
    
    时间复杂度：O(n)
        其中 n 为数组的长度。
        遍历一次数组，更新最大利润。
    空间复杂度：O(1)
*/
class Solution_0 {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }

        int res = 0, curMin = INT_MAX;
        for (int i = 0; i < prices.size(); i++) {
            res = max(res, prices[i] - curMin);
            curMin = min(curMin, prices[i]);
        }
        return res;
    }
};

/*
	股票系列问题
    状态定义：
		dp[i][k][0 or 1]，其中 0 <= i <= n - 1, 1 <= k <= K，
		n 为天数，K 为交易数的上限，0 和 1 代表是否持有股票。
	通用状态转移方程：
		dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
		            = max(今天选择 rest, 今天选择 sell）
        dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
                    = max(今天选择 rest, 今天选择 buy)
    base case：
    	dp[-1][...][0] = dp[...][0][0] = 0
    	dp[-1][...][1] = dp[...][0][1] = -infinity
    	
    特化到 k = 1 的情况
    状态转移方程：
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp[i][1] = max(dp[i-1][1], -prices[i])
    base case：
        dp[i][0] = 0
        dp[i][1] = -prices[i]
    
    时间复杂度：O(n)
        其中 n 为天数，k 为交易数的上限。
        遍历一次数组，更新状态数组。
        k = 1 时，时间复杂度为 O(n)。
        k > 1 时，时间复杂度为 O(nk)。
    空间复杂度：O(n)
        状态数组的大小为 nk。
        k = 1 时，空间复杂度为 O(n)。
        k > 1 时，空间复杂度为 O(nk)。
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(2));
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                // base case
                f[i][0] = 0;
                f[i][1] = -prices[i];
                continue;
            }
            f[i][0] = max(f[i-1][0], f[i-1][1] + prices[i]);
            f[i][1] = max(f[i-1][1], -prices[i]);
        }
        return f[n-1][0];
    }
};

/*
    思路同上，优化空间

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution_2 {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // base case
        int f_i_0 = 0, f_i_1 = INT_MIN;
        for (int i = 0; i < n; i++) {
            f_i_0 = max(f_i_0, f_i_1 + prices[i]);
            f_i_1 = max(f_i_1, -prices[i]);
        }
        return f_i_0;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> test_cases = {
        {7, 1, 5, 3, 6, 4},
        {7, 6, 4, 3, 1}
    };

    for (auto& prices : test_cases) {
        cout << "Input: ";
        for (int price : prices) {
            cout << price << " ";
        }
        cout << endl;
        cout << "Output: " << solution.maxProfit(prices) << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   一次遍历：
       遍历价格数组，同时维护两个变量：
           minPrice：记录遍历过程中遇到的最低价格。
           maxProfit：记录遍历过程中遇到的最大利润。
   更新逻辑：
       对于每个价格 price：
           如果 price 小于 minPrice，更新 minPrice。
           否则，计算当前价格与 minPrice 的差值，如果这个差值大于 maxProfit，则更新 maxProfit。
   返回结果：
       遍历结束后，maxProfit 即为最大利润。

   时间复杂度：O(n)
       遍历一次价格数组，时间复杂度为 O(n)，其中 n 是价格数组的长度。
   空间复杂度：O(1)
       使用了常数级别的额外空间，空间复杂度为 O(1)。
*/
// maxProfit 计算买卖股票的最佳时机，返回最大利润
func maxProfit(prices []int) int {
    if len(prices) == 0 {
		return 0
	}

	minPrice := prices[0]  // 初始化最小价格为第一天的价格
	maxProfit := 0         // 初始化最大利润为 0
	for _, price := range prices {
		if price < minPrice {
			minPrice = price  // 更新最小价格
		} else if price - minPrice > maxProfit {
			maxProfit = price - minPrice  // 更新最大利润
		}
	}
	return maxProfit
}

func main() {
	// 测试用例
	testCases := []struct {
		prices   []int
		expected int
	}{
		{
			prices:   []int{7, 1, 5, 3, 6, 4},
			expected: 5,
		},
		{
			prices:   []int{7, 6, 4, 3, 1},
			expected: 0,
		},
		{
			prices:   []int{},
			expected: 0,
		},
	}

	for i, tc := range testCases {
		result := maxProfit(tc.prices)
		fmt.Printf("Test Case %d, Input: prices = %v\n", i+1, tc.prices)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}