LeetCode 刷题笔记 - 第二期

今天记录一道题目，距离上一次做题应该有一个多月了，没错，我就是这么的没有毅力…

今天这道题目，开始看标题的时候觉得应该蛮难的，看完题目觉得还好，做完之后觉得也挺简单的，然后再思考一会儿觉得原来这么简单啊…题目如下：

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

大致意思就是，给定一个数组，里面的每一个元素为一天的股票价格，然后设计算法怎么样能够最大化收益。但是不能同时参与多笔交易，也就是说必须卖出之后才能买入。

例如，数组为 [1, 3, 4, 5]，那么最大利润则为 4，即 1 买入，5 卖出。

思考

看标题 买卖股票的最好时机 应该是蛮高端困难的问题，但是看完题目，其实就是一个数组计算的问题，要是实际股票要是能这样操作，做梦都能乐醒了-.-

废话不多说，这道题目其实就是要检查每一个元素，如果后一个元素比前一个元素小就卖掉，反之买入或者持有（因为同时只能参与一笔交易），按照这种思路，代码如下：

func maxProfit(prices []int) int {
  var buy, profit int
  var isHold bool = false
  for i := 0; i < len(prices) - 1; i++ {
    if prices[i + 1] > prices[i] && !isHold {
      buy = prices[i]
      isHold = true
    } else if prices[i + 1] < prices[i] && isHold {
      profit += prices[i] - buy
      buy = 0
      isHold = false
    }
  }
  if isHold {
    p := prices[len(prices) - 1] - buy
    profit += p
  }
  return profit
}

buy 和 profit 分别表示买入价格和持有的利润，isHold 表示当前为持有状态还是卖出状态，因为当价格为 0 的时候买入和卖出的状态都是 0。当下个价格比当前价格大并且当前为没有持有的状态时，买入；当下个价格比当前价格小并且当前为持有状态时，卖出。卖出时计算利润，并且重置 buy 和 isHold。

再思考

上面的算法已经可以满足题目要求，而且在时间复杂度上也较为理想，（上面算法的时间复杂度为 O(n)），但是，看来看去，实现的都感觉十分繁琐，所以要再考虑有没有更简洁的算法，既要满足时间复杂度和题目要求，同时也要满足代码的优雅度。

再次审题，其实可以发现题目没有限制交易次数，也就是说我们每次遍历发现后面一个比前面一个小就卖出，反之买入。

代码如下:

func maxProfit(prices []int) int {
  profit := 0
  for i := 1; i < len(prices); i++ {
    if prices[i] - prices[i - 1] > 0 {
      profit += prices[i] - prices[i - 1]
    }
  }
  return profit
}

这样代码看上去比之前的优雅好多，而且时间复杂度也是和之前一样的。

小结

虽然从效率上来讲前后两个算法没有相差多少，但是从代码简洁性看后面的方法要好太多了。但是从思考上可能前者更符合读题时的思路。所以以后在思考上要跳出常规的思维，换一个角度去思考可能会有更好的效果。