這道題要求的一個min和一個max,只是這個min所在的位置要在max所在位置的左邊。
有一種做法是采用蠻力算法,也就是通過從左往右遍歷,把每一個元素都當做min,然后再在這個元素的右邊找一個最大值,這樣得到一個profit,最后求得所有情況中profit的最大值即刻。但是這種做法的時間復雜度是O(n^2);
另一種做法是通過時間換空間的方法,我先用兩個數組:數組1和數組2,數組1[i]表示從prices的第0個數到第i個數的最小值,數組2[i]表示從prices的第[len-1]個數到第i個數的最大值。
這種做法的時間復雜度是O(n),但是空間復雜度也是O(n).
LEETCODE,所以如果有人想出時間復雜度是O(n),且空間復雜度是O(1), 請告訴我下啊!!!
下面是另一種做法的AC代碼:
1 /** 2 * Say you have an array for which the ith element is the price of a given stock on day i. 3 * If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), 4 * design an algorithm to find the maximum profit. 5 * @param prices 6 * @return 7 */ 8 public int maxProfit(int[] prices) { 9 if(prices==null || prices.length <= 1) 10 return 0; 11 int len = prices.length; 12 //ma keep the minimum number till now. 13 int[] ma = new int[len]; 14 //mia keep the maximum number from the end to now 15 int[] mia = new int[len]; 16 ma[0] = prices[0]; 17 for(int i=1;i<len;i++){ 18 if(prices[i]>ma[i-1]) 19 ma[i] = ma[i-1]; 20 else 21 ma[i] = prices[i]; 22 } 23 mia[len-1] = prices[len-1]; 24 for(int i = len-2;i>=0;i--){ 25 if(prices[i]>mia[i+1]) 26 mia[i] = prices[i]; 27 else 28 mia[i] = mia[i+1]; 29 } 30 int max=0; 31 for(int i=0;i<len;i++){ 32 max= mia[i]-ma[i]>max? mia[i]-ma[i]:max; 33 } 34 return max; 35 }
?