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

LeetCode - Best Time to Buy and Sell 2

2024-07-02 09:52:07   225人阅读

这道题我一开始想到用递归方法，可以把规模大的问题变成规模小的问题，但是觉得递归的时间复杂度很高，因为它会把相同的问题进行重复计算，然后我想是不是有什么down-up的方法，先把所有的子问题的结果保存起来，但是发现问题的最优解并不能由子问题的最优解推导出来。最后就想到买股票的时候，我们在一个局部极小的时候买进，然后在一个局部极大的时候卖出，这样就可以通过多次买进卖出交易获得最大收益。接下来的问题就是，确定什么时候是极小值，什么时候是极大值。

下面是AC代码：

 1     /**
 2      * Design an algorithm to find the maximum profit. You may complete as many transactions as you like 
 3      * (ie, buy one and sell one share of the stock multiple times).
 4      *  However, you may not engage in multiple transactions at the same time 
 5      *  (ie, you must sell the stock before you buy again).
 6      * @param prices
 7      * @return
 8      */
 9     public int maxProfit2(int[] prices){
10         if(prices==null || prices.length <= 1)
11             return 0;
12         int profit = 0;
13         int len = prices.length;
14         //the local minimum is marked as -1;the local maximum is marked as 1; otherwise is 0
15         int[] mark = new int[len];
16         int[] left = new int[len];//mark whether the left is <= or >=
17         int[] right = new int[len];//mark whether the right is <= or >=
18         // the first number is initialized as 0
19         left[0] = 0;
20         //get the left array, by one traversal
21         int i=1;
22         while(i<len){
23             if(prices[i-1]<prices[i])
24                 left[i] = -1;
25             else if(prices[i-1]>prices[i])
26                 left[i] = 1;
27             else
28                 left[i] = left[i-1];
29             i++;
30         }
31         //initialize the last element 
32         right[len-1] = 0;
33         i = len-2;
34         while(i>=0){
35             if(prices[i+1]<prices[i])
36                 right[i] = -1;
37             else if(prices[i+1]>prices[i])
38                 right[i] = 1;
39             else
40                 right[i] = right[i+1];
41             i--;
42         }
43         //get the mark
44         i = 0;
45         while(i<len){
46             if(left[i] == right[i]){
47                 mark[i] = left[i]*(-1);
48             }else {
49                 if(left[i] == 0){
50                     mark[i] = right[i]*(-1);
51                 }
52                 else if(right[i] == 0)
53                         mark[i] = left[i]*(-1);
54                 else
55                     mark[i] = 0;
56             }
57             i++;
58         }
59         int buy=0 ,sell = 0;
60         boolean f1 = false, f2 = false;
61         for(i=0;i<len;i++){
62             if(f1==false && mark[i] == -1)//at the minimum time buy.
63             {
64                 buy = prices[i];
65                 f1 = true;
66             }
67             if(f2 == false && f1 == true && mark[i] == 1)//at the maximum time sell, by the condition that we have bought the stock;
68             {
69                 sell = prices[i];
70                 f2 = true;
71             }
72             if(f1 && f2)
73             {
74                 profit += (sell - buy); 
75                 f1 = false;
76                 f2 = false;
77             }
78         }
79         return profit;
80      }

 


联系
我们