博客
关于我
L121买卖股票的最佳时机
阅读量:215 次
发布时间:2019-02-28

本文共 2106 字,大约阅读时间需要 7 分钟。

买卖股票的最佳时机

问题分析

给定一个数组,数组中的每个元素表示某只股票在该天的价格。我们需要找出一笔最优的交易,即买入和卖出股票一次,计算能获得的最大利润。注意,只能完成一笔交易,且卖出价格必须大于买入价格。如果没有这样的交易,利润为0。

方法一:暴力方法

暴力方法通过两重循环遍历所有可能的买入和卖出组合,计算每一笔交易的利润,找出最大值。这种方法的时间复杂度为O(n²),适用于小规模数据,但对于大数组效率较低。

public int maxProfit(int[] prices) {    int len = prices.length;    if (len == 0) return 0;    int max = Integer.MIN_VALUE;    for (int i = 0; i < len; i++) {        for (int j = i; j < len; j++) {            if (max < prices[j] - prices[i]) {                max = prices[j] - prices[i];            }        }    }    return max;}

方法二:记录最小值

通过一次遍历记录最小价格,然后在遍历过程中计算当前价格与最小价格的差值,找出最大利润。这种方法的时间复杂度为O(n),空间复杂度为O(1),效率较高。

public int maxProfit(int[] prices) {    if (prices == null || prices.length == 0) return 0;    int minPrice = Integer.MAX_VALUE;    int maxProfit = 0;    for (int i = 0; i < prices.length; i++) {        if (prices[i] < minPrice) {            minPrice = prices[i];        }        int currentProfit = prices[i] - minPrice;        if (currentProfit > maxProfit) {            maxProfit = currentProfit;        }    }    return maxProfit;}

方法三:动态规划

使用动态规划来解决问题。我们定义两个状态:dp[i][0]表示到第i天结束时不持有股票的现金金额;dp[i][1]表示到第i天结束时持有股票的现金金额。通过状态转移,计算最终的最大利润。

public int maxProfit(int[] prices) {    if (prices == null || prices.length == 0) return 0;    int len = prices.length;    if (len < 2) return 0;    int[][] dp = new int[len][2];    dp[0][0] = 0;    dp[0][1] = -prices[0];    for (int i = 1; i < len; i++) {        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);        dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);    }    return dp[len - 1][0];}

方法四:优化空间复杂度

通过压缩动态规划的空间复杂度,只需维护两个变量,分别表示前一天的不持有和持有股票的情况。

public int maxProfit(int[] prices) {    if (prices == null || prices.length == 0) return 0;    int len = prices.length;    if (len < 2) return 0;    int hold = -prices[0];    int cash = 0;    for (int i = 1; i < len; i++) {        int newHold = Math.max(hold, hold + prices[i]);        int newCash = Math.max(cash, -prices[i]);        hold = newHold;        cash = newCash;    }    return cash;}

总结

通过上述方法,我们可以高效地解决买卖股票的最佳时机问题。记录最小值和动态规划方法均以O(n)时间复杂度和O(1)空间复杂度,适用于大规模数据处理。

转载地址:http://cjvp.baihongyu.com/

你可能感兴趣的文章
Python中的多个元组到两对元组?
查看>>
Python中的多态性
查看>>
PYTHON中的套接字与多处理.Connection.Listener
查看>>
Python中的子句提取/长句切分
查看>>
python中的字符串比较但不是Levenshtein距离(我认为)
查看>>
python中的字符范围
查看>>
Python中的文本和字节序列
查看>>
python中的方法_Python中看起来高大上的技术
查看>>
PYTHON中的测地距离变换
查看>>
Python中的私有方法
查看>>
Python中的空元组是“常量“吗?
查看>>
Python中的类-ChatGPT4o作答
查看>>
Python中的类中的池
查看>>
python中的装饰器基础
查看>>
python中的负零
查看>>
Python中的进程通信
查看>>
Python中的递归有多安全?
查看>>
python中程序如何获取实现多行输入
查看>>
python中算法与数学_中国古代数学算法的Python实现
查看>>
python中类的实例化_python类的实例化
查看>>