LeetCode - Algorithms - 121. Best Time to Buy and Sell Stock

虽然难度标为Easy，但自己居然提交了好几次才通过了，而且是因为犯了逻辑错误。最后用个二重循环，倒也简单，但性能不好，不知道高效算法是如何做的？

Java

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

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 4.30 % of java submissions.

在网上人家的一个O(n)时间复杂度的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
    	if (prices==null || prices.length<=1)
    		return 0;
        int r = 0;
        int minPrice = prices[0];
        for(int i=1;i<prices.length;i++) {
        	r = Math.max(r, prices[i]-minPrice);
        	minPrice = Math.min(minPrice, prices[i]);
        }
        return r;        
    }
}

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 32.88 % of java submissions.

JavaScript

O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
	if (prices==null || prices.length==0)
		return 0;
	var r=0;
	var x = 0;
	for(var i=0;i<prices.length-1;i++) {
		for(var j=prices.length-1;j>i;j--) {
			x = prices[j]-prices[i];
			if (x>r)
				r = x;
		}
	}
	return r;    
};

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 7.71 % of javascript submissions.

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
	if (prices==null || prices.length<=1)
		return 0;
	var r=0;
	var minPrice = prices[0];
	for(var i=1;i<prices.length;i++) {
		r = Math.max(r,prices[i]-minPrice);
		minPrice = Math.min(minPrice,prices[i]);
	}
	return r;    
};

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 84.89 % of javascript submissions.