首页 > 代码库 > LeetCode - Best Time to Buy and Sell

LeetCode - Best Time to Buy and Sell

2024-07-02 07:20:47   223人阅读

这道题要求的一个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).

所以如果有人想出时间复杂度是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     }

 


联系
我们