LeetCode精选TOP面试题122.买卖股票的最佳时机II

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路

• 思路1 ：一步一计算
  定义入手价格变量 in ，遍历数组，判断当前元素item与in的大小关系，如果item > in， 那么直接卖出，利润累加；如果item < in， 更新in为item，表示可以用比之前更低的价格买入。
  考虑以下两种情况：
  股票一路走低，那就直接不用买了，只更新in，但是利润不要累加；
  股票一路走高，那就每次都第二天先卖出赚利润后再买入，利润不断累加，符合题意，并可以引出思路2。
• 思路2：只计算上升曲线，
  啥意思呢？
  就是只考虑思路1的第二步，当今天的股价比前一天高，就把差价累加到利润中，很明显，当股票走低转折的时候，作为买家我是不会在前一天购买的，这其实并不合理，因为股价很难预测，但是题目要求是根据给定数组推算利润，所以这是可行的。

  代码实现（Java）

  /**
   * @author : flower48237
   * @2020/3/16 17:23
   * title : LeetCode精选TOP面试题122.买卖股票的最佳时机II
   */
  public class Solution {
      public int maxProfit(int[] prices) {
          if (prices.length == 0){
          	// 判断数组是否为空
              return 0;
          }
          int interest = 0; // 利润初始化为0
          // 法1
          int in = prices[0];
          for (int i = 1; i < prices.length; i++){
              if (prices[i] > in){
              	// 那么直接卖出，利润累加
                  interest += prices[i] - in;
                  // 更新入手价in
                  in = prices[i];
              }else if (prices[i] < in){
              	// 更新入手价in
                  in = prices[i];
              }
          }
          
          // 法 2
          for (int i = 1; i < prices.length; i++){
              if (prices[i] > prices[i - 1]){
              	// 只计算上升曲线，差价累加
              	// 很容易考虑如果在曲线图内，连续的差值实际上就等于
              	// 波峰-波谷 = 极高价卖出 - 极低价买入
                  interest += prices[i] - prices[i - 1];
              }
          }
          return interest;
      }
  }

  其实就是贪心算法的思路

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/bbd4b07b.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。