数组算法 - 买卖股票的最佳时机

买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode） 刷题时间:

• 25/12/25

我的解法

▼
java
复制代码
class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;

        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int cha = prices[j] - prices[i];
                max = (cha > max) ? cha : max;
            }
        }

        return max;
    }
}

优点

• 逻辑简单直接
• 计算了所有可能的组合

缺点

• 时间复杂度高. $O(n^2)$
• 重复计算, 内层循环重复计算了很多信息, 事实上,找到最低价格即可.
• 没有利用到题目问题的信息

题解

▼
java
复制代码
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int minPrice = Integer.MAX_VALUE;  // 最低价格
        int maxProfit = 0;  //最大利润

        for (int price : prices) {
	        // 更新最低价格
            minPrice = price < minPrice ? price : minPrice;
            int profit = price - minPrice;   // 当前价格所得利润
            // 更新最大利润
            maxProfit = profit > maxProfit ? profit : maxProfit;
        }

        return maxProfit;
    }
}

思路

• 我的解法是两层循环,找到一对数据(i，j),计算比较出最大利润, 暴力解法
  • 时间复杂度是$O(n^2)$,空间复杂度是$O(1)$. 方向就是减少内层循环, 降为$O(n)$.
• 题目信息: "最低点买入,最高点卖出", 内层循环的目的是"找到所有组合,比较出最大利润".
  • 核心就是记录历史最低价格
  • 用空间换时间, 用变量来存储minPrice(历史最低价格)即可, 一次遍历,用price逐个与minPrice进行比较, 得到差值profit.
  • 就可以找到maxProfit.

算法思想

• 贪心思想
  • 在每一步选择中都采取当前状态下最优(最有利)的选择, 从而希望导致全局最优解的算法思想
  • 1. 局部最优 -> 全局最优
    • • 每次更新历史最低价总是正确的; 每次更新最大利润总是正确的
  • 2. 不可撤回: 当遇到最低价时, 就忘记之前的最低点; 只关注"到现在为止的最低点".
  • 3. 高效但不通用: 时间复杂度低, 但是不是所有问题都能用贪心解决

其他算法解法 后面有机会了, 再重新写写

• 动态规划
  • 这个没看
• 单调栈
  • 这个看了, 但是有点难理解