leetcode best-time-to-buy-and-sell-stock(Java)

leetcode題目

best-time-to-buy-and-sell-stock – newcoder 30

買賣股票的最佳時機 – leetcode 121

題目描述

* 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 天的價格。
 * 如果你最多隻允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能擷取的最大利潤。
 * 
 * 注意你不能在買入股票前賣出股票。
 * 
 * 示例 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。
           

思路

* 思路1：(貪心算法)
 * 1、初始化數組的第一個元素為最低價格
 * 2、從左到右周遊，更新最低價格，更新最大收益值
 * 
 * 思路2：
 * 1、用sell表示初始時的利潤為0，buy表示最便宜股票的價格
 * 2、從左到右周遊，buy表示前些天買入最便宜股票的股價
 * 3、sell儲存前些天買入最便宜股票後再在股票最高時賣出股票的最大利潤
 * 延伸：
 * 此思路可類推進行兩次交易的最大利益。
           

代碼

package com.leetcode.array;

/**
 * 題目：
 * best-time-to-buy-and-sell-stock -- newcoder 30  
 * 買賣股票的最佳時機 -- leetcode 121
 * 
 * 題目描述：
 * 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 天的價格。
 * 如果你最多隻允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能擷取的最大利潤。
 * 
 * 注意你不能在買入股票前賣出股票。
 * 
 * 示例 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 BestTimeToBuyAndSellStock {

	/**
	 * 思路：(貪心算法)
	 * 1、初始化數組的第一個元素為最低價格
	 * 2、從左到右周遊，更新最低價格，更新最大收益值
	 * 
	 * @param prices 股票價格數組
	 */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
        	return 0;
        }
        
        // 最低價格
        int min = prices[0];
        // 最大收益
        int maxProfit = 0;
        
        for (int i=1, len = prices.length; i<len; i++) {
        	int cur = prices[i];
        	// 更新最低價格
        	if (cur <= min) {
        		min = cur;
        	// 更新利潤
        	} else {
        		maxProfit = Math.max(maxProfit, cur - min);
        	}
        }
        	
        return maxProfit;
    }
	
    /**
     * 思路：
     * 1、用sell表示初始時的利潤為0，buy表示最便宜股票的價格
     * 2、從左到右周遊，buy表示前些天買入最便宜股票的股價
     * 3、sell儲存前些天買入最便宜股票後再在股票最高時賣出股票的最大利潤
     * 
     * 延伸：
     * 此思路可類推進行兩次交易的最大利益。
     */
    public int maxProfit2(int[] prices) {
    	if (prices == null || prices.length <= 1) {
    		return 0;
    	}
    	
    	// 記錄最便宜股票的價格(買入即利潤為負值)
    	int buy = -prices[0];
    	// 記錄利潤
    	int sell = 0;
    	
    	for (int i=0, len=prices.length; i<len; i++) {
    		// 更新最低價格
    		buy = Math.max(buy, -prices[i]);
    		// 更新利潤
    		sell = Math.max(sell, prices[i] + buy);
    	}
    	
    	return sell;
    }
    
	public static void main(String[] args) {
		int[] arr1 = {7, 1, 5, 3, 6, 4};
		System.out.println(new BestTimeToBuyAndSellStock().maxProfit(arr1));
		System.out.println(new BestTimeToBuyAndSellStock().maxProfit2(arr1));		
		int[] arr2 = {7, 6, 4, 3, 1};
		System.out.println(new BestTimeToBuyAndSellStock().maxProfit(arr2));
		System.out.println(new BestTimeToBuyAndSellStock().maxProfit2(arr2));		
	}

}

           

相關題目：

【best-time-to-buy-and-sell-stock-ii】

【best-time-to-buy-and-sell-stock-iii】