leetcode : Best Time to Buy and Sell Stock

 

最近看到网站上提到了leetcode网站，用来在线面试算法；就上去看了下，自己也解决了一题，蛮有意思的，偶尔做做算法练练脑。

题目：Best Time to Buy and Sell Stock

 

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

 

大致的意思就是输入一个股票的股价数组，第i个元素代表第i天的股价，只允许买入卖出一次，问最大的利润是多少？

 

 

第一个反映和解决：

两层for循环遍历下即可，在浏览器中输入完成；提交"judge small"按钮，提示有非法字符；排除后，正确运行。代码如下：

 

public class Solution {
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        //check the input
        if(prices==null||prices.length<=1){
            
            return 0;
        }
        
        
        //proces
        int max = 0;
        int buyPoint = 0;
        int sellPoint = 1;
        

        for (int j=0;j<prices.length -1;j++){
            buyPoint = j;
            for (int i=j+1;i<prices.length;i++){
                sellPoint = i;
                if (prices[i]-prices[j]>max){
                    max = prices[i]-prices[j];
                    sellPoint = i;
                }
            }
        }
        
        
        
        // not buy 
        if (max<0){
            return 0;
        }
        
        return max;
        
    }
}

 

 

但是当按"judge large"时，提示 运行超时:(

 

第二解决：

思考了下 o(N平方)，能不能降到N(log N)，花了大概5分钟思考和验证（算法知识已经遗忘了很多），居然找出了o(N)的算法：

1先找出股价最小值和股价最大值的位置，

1.1如果股价最小点的位置在股价最大值的位置之前，直接输出最大值和最小值的差，程序结束；

1.2 反之，三段式处理。

2，三段式处理：

2.1 从数组开始点到“股价最大值的位置”这一区间，只要找到这一段的最小值，然后和之前的最大值相减，就是这段可能的最大利润；P1

2.2 从"股价最小点的位置"到数组的结尾这一区间，只要找到这一段的最大值，冉舟和之前的最小值相减，就是这一段可能的最大李瑞：P3

2.3“股价最大值的位置”到"股价最小点的位置"这一区间，这段区间为止，递归解决；P2

 

编程好程序，再执行，还是提示超时。。。这个算法的的复杂度是O(N)啊，应该不可能有再快的算法了。突然想到java对递归支持不好，如果数据很长的话，可能StackOverFlow。

 

最终版本：

那就改成非递归的版本吧，改完再测试，果然ok了。

代码如下：

 

public class Solution {
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        //check the input
        if(prices==null||prices.length<=1){
            return 0;
        }
    
           
        int start = 0;
        int end = prices.length-1;
        int max = 0;
        
        
        while (end - start >=1){
            //find the smallest and biggest
            int smallest = prices[start];
            int sPoint = start;
            int biggest = prices[start];
            int bPoint = start;
            for (int i=start+1;i<=end;i++){
                if (prices[i]<smallest){
                    smallest = prices[i];
                    sPoint = i;
                }
                
                if (prices[i]>biggest){
                    biggest = prices[i];
                    bPoint = i;
                }
                
            }
    
            if (sPoint<bPoint){
                if (biggest-smallest>max){
                    max = biggest - smallest;
                } 
                break;          
            }
            
            
            // find the smallest in the interval
            int p1 = 0;
            int s1 = biggest;
            for (int i=start;i<bPoint;i++){
                if (prices[i]<s1){
                    s1 = prices[i];
                }
            }
            p1 = biggest -s1;
            if (p1>max){
                max = p1;
            }
            
            
            // find the smallest in the third interval        
            int p3 = 0;
            int b1 = smallest;
            for (int i=sPoint+1;i<=end;i++){
                if (prices[i]>b1){
                    b1 = prices[i];
                }
            }
            p3 = b1 - smallest;
    
            if (p3>max){
                max = p3;
            }
             
            //find the smallest in the second interval
            start = bPoint+1;
            end = sPoint-1;

        }
        


        // not buy 
        if (max<0){
            return 0;
        }
        
        return max;
        
    }
            
    
}

 

 

 

 

小结：

1）使用在线文本编辑器后，才知道Eclipse的好啊，一些无聊的错误在eclipse中根本就不会发生，而且如果有问题，直接输入异常，真的不行debug下就知道原因了；

2）leetcode网站的题目质量还是很高的；

3）这种方式的面试确实对动手能力要求很高（类ACM），而且能绕过一些麻烦的环境准备问题，对面试过程确实有帮助。

 

 

评论

2 楼 wtnbmy_aaaeau 2015-08-04  

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int num_days = prices.size();
        if(num_days == 0) {
            return 0;
        }

        int max_profit = 0;
        int lowest_price = prices[0];

        for(int i=1; i<num_days; i++) {

            int profit_tmp = prices[i]-lowest_price;
            if(profit_tmp > max_profit) {
                max_profit = profit_tmp;
            }

            if(prices[i] < lowest_price) {
                lowest_price = prices[i];
            }
        }

        return max_profit;
    }
};

1 楼 花与剑 2014-06-21  

兄台，你这个非递归的程序算法的复杂度不是o(N).Bad 的 情况是O(N^2)
比如：
64，32，16，8，4，2，1.
复杂度是
o(7)+o(5)+o(3)+o(1) = 16