阅读量:0
买卖股票的最佳时机 ||
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 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 = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。 最大总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。
解题思路：这题和昨天的买卖股票的最佳时机一题很类似，只是在此基础上，增加了需求，从只能买一次股票变成可以多次购买实现利润最大化。
实现思路一：常规思路
从左到右遍历数组，同时维护一个最小买入价格 min_price 和及时更新最大利润 maxProfit。
以下是 时间复杂度O(n)，空间复杂度 O(1)算法的步骤：
1.初始化 min_price 为第一个元素，即第一天的股票价格。
2.初始化 max_profit 为 0。
3.从第二天开始遍历数组 prices：
（1）对于每个价格 prices[i]，计算如果今天卖出的利润：profit = prices[i] - min_price。
（2）如果 profit 大于 0，则更新 max_profit，同时更新min_price令其等于prices[i]，以便进行下 一轮的买股，卖股。
（3）如果 prices[i] 小于 min_price，则更新 min_price。
4.返回 max_profit。
实现代码：
public int maxProfit(int[] prices) { int min_price=prices[0]; //记录最小价格 int max_profit=0;//记录最大利润值 for (int i = 1; i < prices.length ; i++) { //计算利润 int profit=prices[i]-min_price; //是否为正利润，为正利润则更新 if (profit>0){ max_profit += profit; //min_price 前移，让其等于当前指针的值 min_price=prices[i]; } //更新最小价格 if(min_price>prices[i]){ min_price=prices[i]; } } return max_profit; }思考：如果用昨天所说的买卖股票的最佳时机一题中所补充的Math.max和Math.min函数如何实现本题解题呢？
实现思路二：贪心算法
贪心算法的核心思想是，如果今天的价格比昨天高，就卖出昨天买入的股票。
- 初始化
maxProfit为 0。 - 遍历数组
prices，对于每一天i（从1到数组末尾）： 如果prices[i] > prices[i - 1]，则表示今天的价格比昨天高，可以卖出昨天买入的股票，获得利润prices[i] - prices[i - 1]，并将这个利润加到maxProfit上。
实现代码：
public int maxProfit(int[] prices) { int maxProfit = 0; for (int i = 1; i < prices.length; i++) { // 如果今天的价格比昨天高，就卖出股票 if (prices[i] > prices[i - 1]) { maxProfit += prices[i] - prices[i - 1]; } } return maxProfit; }这段代码的时间复杂度是 O(n)，其中 n 是数组 prices 的长度。这种方法简单且高效，适用于这个问题。在实际应用中，这种方法通常能够获得很好的结果，尤其是当股票价格波动较大时。
小知识补充：贪心算法
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。这种算法不保证会得到最优解，但在某些情况下，贪心算法的解足够接近最优解或者确实是最优解。
贪心算法的关键特点：
- 贪心选择性质：在每一步选择中都采取对当前状态最优的决策。
- 不可逆转：一旦做出贪心选择，就不能再改变。这意味着一旦选择了某个选项，就无法撤销或回退到之前的状态。
- 贪心算法不存储所有可能的候选解，它只考虑当前的候选解。
- 问题分解：贪心算法通过将问题分解为子问题来求解，并且假设子问题的局部最优解能构成全局最优解。
贪心算法适用的情况：
- 优化问题：需要找到最优或次优解的问题。
- 有明确的贪心选择：问题有一个明确的贪心选择策略。
- 贪心选择性质：局部最优选择能够导致全局最优解。
贪心算法的实现步骤：
- 定义问题的解空间：确定所有可能的候选解。
- 贪心选择：根据问题的贪心选择性质，选择当前最优的候选解。
- 更新解空间：使用当前选择的候选解更新解空间，排除那些不再可行的解。
- 循环或递归：重复步骤2和3，直到找到问题的解或解空间为空。
- 输出结果：输出找到的解或报告无解。
例子：
- 货币找零问题：给定不同面额的货币和需要找零的金额，目标是用最少数量的货币完成找零。贪心算法每次选择当前最大面额的货币。
- 霍夫曼编码（Huffman Coding）：一种用于数据压缩的贪心算法，通过构建最优二叉树来为不同的字符分配编码。
- Dijkstra算法：用于在加权图中找到单个源点到其他所有顶点的最短路径。
注意事项：
- 贪心算法并不总是能得到全局最优解，但在某些问题上（如霍夫曼编码和Dijkstra算法）可以保证找到最优解。
- 贪心算法的效率通常很高，因为它避免了存储和搜索所有可能的解。
- 在使用贪心算法时，需要仔细分析问题，确保贪心选择能够导致问题的最优解或可接受的次优解。
