GuangchaoSun's Blog

Leetcode-Bset Time to Bug and Sell Stock

发表于  |    |   分类于   |  

Best Time to Buy and Sell Stock I

题意：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。 如果只允许进行一次交易，也就是说只允许一支股票买一次并卖掉，求最大的收益。

分析：动态规划法。从前向后遍历数组，记录当前出现过的最低价格，作为买入价格，并计算以当天价格出售的收益，作为可能的最大收益，整个遍历过程中，出现过的最大收益就是所求。

  • 找到最小值
  • 找到最大值
  • 最小值要在最大值之前
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int lowest = Integer.MAX_VALUE;
        for(int p:prices){
            lowest = Math.min(lowest,p);
            max = Math.max(p-lowest,max);
        }
        return max;
    }
}

复杂度：时间O(n)，空间O(1)

Best Time to Buy and Sell Stock II

题意：贪心法。从前向后遍历数组，只要当天的价格高于前一天的价格，就算入收益。

分析：贪心法。从前向后遍历数组，只要当天的价格高于前一天的价格，就算入收益。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1) return 0;
        int profit = 0;
        int hold = prices[0];
        for(int i=1; i < prices.length; i++){
            if(hold < prices[i]){
                profit += prices[i] - hold;
            }
            hold = prices[i];
        }
        return profit;
    }
}

复杂度：时间O(n)，空间O(1)

Best Time to Buy and Sell Stock III

题意：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易两次，手上最多只能持有一支股票，求最大收益。

分析：动态规划法。以第i天为分界线，计算第i天之前进行一次交易的最大收益left[i]，和第i天之后进行一次交易的最大收益right[i]，最后遍历一遍，max{left[i] +right[i]} (0≤i≤n-1)就是最大收益。第i天之前和第i天之后进行一次的最大收益求法同Best Time to Buy and Sell Stock I。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution{
	public int maxProfit(int[] prices){
		if(prices.length <= 1) return 0;
		int[] left = new int[prices.length];
		int[] right = new int[prices.length];
		int left_min = prices[0];
		for(int i=1; i < prices.length; i++){
			left_min = Math.min(left_min, prices[i]);
			left[i] = Math.max(prices[i]-left_min, left[i-1]);
		}
		int right_max = prices[prices.length-1];
		for(int i = prices.length-2; i >= 0; i--){
			right_max = Math.max(right_max, prices[i]);
			right[i] = Math.max(right_max-prices[i], right[i+1]);
		}
		int m = 0;
		for(int i=0; i < prices.length; i++){
			m = Math.max(m, left[i]+right[i]);
		}
		return m;
	}
}

复杂度：时间O(n)，空间O(n)

参考

http://blog.csdn.net/ljiabin/article/details/44900389
http://leetcode.tgic.me/best-time-to-buy-and-sell-stock-iii/index.html