121. Best Time to Buy and Sell Stock

在一个数组中是一只股票各天的价格，在只允许交易一次的情况下计算所能获得的最大收益。

思路： 遍历时寻找最小值以及比较最大的差值

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # 6 star, 遍历时寻找最小值以及比较最大的差值
        if len(prices) <= 1:
            return 0
        rs = 0
        low = prices[0]
        for i in prices:
            rs = max(rs, i - low)
            if i < low:
                low = i
        return rs

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 从左到右遍历，start标记当前区间内的最小值，遇到下一个值比start小就更新start的值，遇到比start大就继续往前
// 在遍历中获取当前区间的最大收益，并且与之前的最大收益进行比较，比之前的大，则这就是新的最大收益
func maxProfit(prices []int) int {
	if len(prices) == 0 {return 0}
	start := prices[0]
	profit, curProfit := 0, 0
	for _,val := range prices[1:] {
		if val > start {
			curProfit = val - start
			if curProfit > profit {profit = curProfit}
		} else if val < start {
			start = val
		} else {continue}

	}
	return profit
}