LEETCODE，LeetCode - Best Time to Buy and Sell

2023-10-07 阅读 28 评论 0

摘要：這道題要求的一個min和一個max，只是這個min所在的位置要在max所在位置的左邊。有一種做法是采用蠻力算法，也就是通過從左往右遍歷，把每一個元素都當做min，然后再在這個元素的右邊找一個最大值，這樣得到一個profit，最后求得所有情況

這道題要求的一個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     }