leetcode-121-买卖股票的最佳时机(best time to buy and sell stock)-java

题目与测试

package pid121;
/*买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。*/




public class main {
	
	public static void main(String[] args) {
		int[][] testTable = {{7,1,5,3,6,4},{1,2,3,4,5},{7,6,4,3,1},{1,6,2,7}};
		for (int[] ito : testTable) {
			test(ito);
		}
	}
		 
	private static void test(int[] ito) {
		Solution solution = new Solution();
		int rtn;
		long begin = System.currentTimeMillis();
		for (int i = 0; i < ito.length; i++) {
		    System.out.print(ito[i]+" ");		    
		}
		System.out.println();
		//开始时打印数组
		
		rtn = solution.maxProfit(ito);//执行程序
		long end = System.currentTimeMillis();	
		
		//System.out.println(ito + ": rtn=" + rtn);
		System.out.println( " rtn=" +rtn);
//		for (int i = 0; i < ito.length; i++) {
//		    System.out.print(ito[i]+" ");
//		}//打印结果几数组
		
		System.out.println();
		System.out.println("耗时：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}

           

解法1（成功，速度较快，3ms）

建立一个first 的低价，高价，利润

和second

当没有second时，对first的低高进行初始化和修改

但如果now<firstlow时，进入第二个阶段，得到secondhigh

如果second的profit比first的大，则first变为second的值

最后返回first的profit

package pid121;

class Solution {
    public int maxProfit(int[] prices) {
        
    	int length=prices.length;
    	int firstLow=-1;
    	int firstHigh=-1;
    	int firstProfit=0;
    	int secondLow=-1;
    	int secondHigh=-1;
    	int secondProfit=0;
    	
    	if(length==0||length==1){
    		return 0;
    	}
    	
    	for(int i=0;i<length;i++){
    		/*System.out.println("firstLow="+firstLow);
    		System.out.println("secondLow="+secondLow);
    		System.out.println("firstprofit="+firstProfit);
    		System.out.println("secondprofit="+secondProfit);*/
    		int now=prices[i];
    		if(secondLow==-1){//只有第一种的情况
    			if(firstLow==-1){//初始low
        			firstLow=now;
        			continue;
        		}
        		if(firstHigh==-1&&now>firstLow){//初始high
        			firstHigh=now;
        			firstProfit=firstHigh-firstLow;
        			continue;
        		}
        		if(now>firstHigh&&firstHigh!=-1){//high更大
        			firstHigh=now;
        			firstProfit=firstHigh-firstLow;
        			continue;
        		}
        		if(now<firstLow){
        			secondLow=now;
        			continue;
        		}        	
    		}
    		
    		
    		
    		if(secondLow!=-1){
    			if(secondHigh==-1&&now>secondLow){//初始化high
    				secondHigh=now;
    				secondProfit=secondHigh-secondLow;
    			}
    			if(now>secondHigh&&secondHigh!=-1){//high更高
    				secondHigh=now;
    				secondProfit=secondHigh-secondLow;
    			}
    			if(secondProfit>firstProfit){
    				firstLow=secondLow;
    				firstHigh=secondHigh;
    				firstProfit=secondProfit;
    				secondLow=-1;
    		    	secondHigh=-1;
    		    	secondProfit=0;
    		    	continue;
    			}
    			if(now<secondLow){
    				secondLow=now;
    				secondHigh=-1;
    				secondProfit=0;
    			}
    			
    		}
    		
    	}
    	
    	
    	return firstProfit;
    }
}

           

解法2（成功，1ms，极快）

假设买了第一个，遇到下一个比他价格低就换成下一个是买入的，遇到价格高的就假设卖出，最后多种卖出的情况比较求最值。

也就是最大利润为max(当前的值-之前的min,之前的max利润)

保存min（之前最小的price），maxProfit（之前最大的利润）

不断动态规划

public int maxProfit(int[] prices) {
        //max[i]=max[i-1] /  prices[i]-min[i-1]
    	int length=prices.length;
    	if(length<=1){
    		return 0;
    	}    	
    	int maxProfit=0;
    	int min=prices[0];
    	for(int i=0;i<length;i++){
    		int now=prices[i];
    		if(now-min>maxProfit){
    			maxProfit=now-min;
    		}
    		if(now<min){
    			min=now;
    		}
    	}    	    	
    	return maxProfit;
    }