6.30 Best Time to Buy and Sell Stock

Description

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

---

思路

简单来说，题目中需要找到数组中的最小值与最大值元素，其中最小值元素的位置<最大值元素的位置

minVal maxVal
index(minVal)<index(maxVal)

还有一个关键的地方，从某一个元素开始，往后扫描边计算最大收益时，当遇到的元素要比起始元素小时，期间扫描过的元素无需再考察扫描收益，因为期间的元素必定大于起始元素，则收益必定小于起始元素的收益

[2,4,3,1,9,1,13]
=> 2 --scan--> 4,3 stop -->1 ,, curMaxProfit=4-2=2
skip 4,3 !
=> 1 --scan-->9,1,13 curMaxProfit=13-1=12

leetcode低时间复杂度代码

func maxProfit(prices []int) int {
   // begin, end, max := 0, 0, 0
   var begin, end, max int
   for end < len(prices) {
      profit := prices[end] - prices[begin]
      if profit <= 0 {
         begin = end
      } else if profit > max {
         max = profit
      }
      end++
   }
   return max
}

自己第一次写的代码

对于自己一开始想的算法,时间复杂度较高

思路为对起始元素扫描一个其后面序列的最大值，作为这个元素的最大收益，记录此时的最小元素位置，最大收益，最小元素位置对应的最大元素位置

往后考察，如果 当前元素的位置未越过最大值位置 （由条件得，当最小元素的位置必须在最大元素后）

• 后一个元素的值比前一个最小元素的值小 这个元素作为新的最小元素，更新最小元素位置，最大收益，最小元素位置对应的最大元素位置
• 后一个元素的值比前一个最小元素的值大 最小元素不变动，跳过这个值

如果当前元素的位置越过最大值位置后

从当前元素开始再找其后的最大值（这个算法时间复杂度高的原因，多次扫描找最大值）

重复上述过程

考察情况如下

[3,4,2,13,9,1,10]
=> 3 --scan-->4,3,13,9,1,10 ,, maxProfit=13-3=10 , minPos=0,mapAfter[minPos]=index(13)=3
=> 4 skip
=> 2 , maxProfit=10+(3-2)=11 ,mapAfter[minPos]=mapAfter[minPos(old)], minPos=1,
=> 13 skip
=> 9 --scan-->1,10 !!这里就和第一步扫描1,10发生了重复!!  由于10-1=9<maxProfit=10 所以无变化
=> 10 --scan--> nothing 

func maxProfit(prices []int) int {
   if len(prices) <= 1{
      return 0
   }
   maxAfter := make(map[int]int)
   curMaxProfit := 0
   curMinPos := -1
   for i:=0;i<len(prices);i++ {
      flag := prices[i]
      //cur pos less or equal than the max position && cur val less than the value of the past min pos   so
      if maxAfter[curMinPos] !=0 && i<=maxAfter[curMinPos]{
         if flag<prices[curMinPos] {
            curMaxProfit += prices[curMinPos] - flag
            maxAfter[i] = maxAfter[curMinPos]
            curMinPos = i
            //fmt.Println(i," ",curMaxProfit)
            continue
         }
         //skip the value which bigger or equal than the minPos value
         continue
      }

      tmpMax := flag
      maxPos := i+1
      for j:=maxPos;j<len(prices);j++ {
         if prices[j]>tmpMax {
            tmpMax = prices[j]
            maxPos = j
         }
      }
      //no val bigger than flag
      if tmpMax-flag <= curMaxProfit {
         continue
      }
      curMinPos = i
      curMaxProfit = tmpMax-flag
      //fmt.Println(maxPos," - ",curMaxProfit)
      //record start pos & his max pos
      maxAfter[i]=maxPos
   }
   //fmt.Println(maxAfter)
   return curMaxProfit
}

总结

对于自己第一次写的代码，问题来自与最大元的重复查找，对每一个考察的元素，每次查找其最大元都要扫描一次其后的元素

相比于leetcode上的代码，对每一个考察的元素，在扫描过程中如果发现比它更小或相同的元素后，即将该元素位置作为新的起始点(最小元)，继续往后考察最大元，这样考察扫描最大元就不会有重复扫描的问题