Say you have an array for which the i<sup style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; top: -0.5em;">th element is the price of a given stock on day i.
給定一個(gè)數(shù)組陆馁，其中第i個(gè)元素是第i天是這個(gè)股票的價(jià)格
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.
如果你僅被允許交易一次（即買一支股票和賣一支股票）陕赃，設(shè)計(jì)一個(gè)算法來(lái)找到最大的利潤(rùn)
這個(gè)題目有點(diǎn)繞翁都，其實(shí)就是在一個(gè)數(shù)組中找到差值（利潤(rùn)）最大的兩個(gè)數(shù)，但是關(guān)鍵在于題目設(shè)定的賣出的價(jià)格必須大于買進(jìn)的價(jià)格，也就是后面的數(shù)要大于前面的數(shù)澜汤，這就難了械筛，如果是通常的判斷，勢(shì)必要每一個(gè)數(shù)都要判斷一遍，因?yàn)檫€沒(méi)有循環(huán)到后面的事后你不知道到底后面有沒(méi)有更大的數(shù)
For example 1
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
For example 2
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
My Solution
(Java) Version 1 Time: Time Limit Exceeded:
樸素的超時(shí)的方法
public class Solution {
public int maxProfit(int[] prices) {
int min=0;
for(int i=0;i<prices.length-1;i++){
for(int j=i+1;j<prices.length;j++){
int temp=prices[i]-prices[j];
if(temp<min)min=temp;
}
}
return -min;
}
}
(Java) Version 2 Time: 2ms:
解決超時(shí)的問(wèn)題诡曙，首先肯定是減小計(jì)算量臀叙，我們可以發(fā)現(xiàn)在超時(shí)算法中有很多不必要的判斷步驟，比如[1,2,3,4]中价卤，如果我們找到了1和4那么判斷2,3顯然是多余劝萤，所以可以以找到的第一個(gè)最大的數(shù)為界（這個(gè)數(shù)的下一個(gè)比它小）慎璧，然后計(jì)算多個(gè)“最大值”然后比較這些最大值找到最大的值
public class Solution {
public int maxProfit(int[] prices) {
if(prices.length==1||prices.length==0)return 0;
int max=0,tempmax=0,a=prices[0],b=prices[0];
for(int i=1;i<prices.length;i++){
if(prices[i]>b){
b=prices[i];
tempmax=b-a;
}else if(prices[i]<a){
max=tempmax>max?tempmax:max;
a=prices[i];
b=prices[i];
tempmax=b-a;
}else{
continue;
}
}
return tempmax>max?tempmax:max;
}
}
(Java) Version 3 Time: 2ms (By reddy2005):
從頭開(kāi)始遍歷床嫌，遇到小于min的就存下了，遇到大于min的就把這個(gè)數(shù)減去min的差保存下來(lái)胸私，然后讓max在后面跟著判斷厌处，找到最大的
public class Solution {
public int maxProfit(int[] prices) {
int len=prices.length;
if(len==0) return 0;
int min=prices[0],max=0;
for(int i=0;i<len;i++){
if(prices[i]<min) min=prices[i];
prices[i]-=min;
if(max<prices[i]) max=prices[i];
}
return max;
}
}
(Java) Version 4 Time: 3ms (By tiffanyTown):
據(jù)說(shuō)這是一個(gè)DP解法，然而DP我并不是很懂岁疼，所以只能留到以后再看了
public class Solution {
public int maxProfit(int[] prices) {
if(prices.length<2) return 0;
int[] dp=new int[prices.length];
int minPrice=prices[0];
dp[0]=0;
for(int i=1;i<prices.length;i++){
if(prices[i]>=minPrice){
dp[i]=Math.max(dp[i-1],prices[i]-minPrice);
}
else{
minPrice=prices[i];
dp[i]=dp[i-1];
}
}
return dp[prices.length-1];
}
}
(Java) Version 5 Time: 3ms (By anton15):
總有些人就是想搞個(gè)大新聞阔涉，瘋狂使用Java自帶函數(shù)，來(lái)達(dá)到盡可能少的代碼捷绒，這很6
/*
*Proper Java - 6 lines:
*/
public class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE, max = 0;
for (int i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i]);
max = Math.max(max, prices[i] - min);
}
return max;
}
}
/*
*Proper Java with shortcuts - 4 lines:
*/
public class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE, max = 0;
for (int i = 0; i < prices.length; i++)
max = Math.max(max, prices[i] - (min = Math.min(min, prices[i])));
return max;
}
}
/*
*Java 8 streams - 2 lines:
*/
public class Solution {
int min = Integer.MAX_VALUE;
public int maxProfit(int[] prices) {
return Arrays.stream(prices).map(i -> i - (min = Math.min(min, i))).max().orElse(0);
}
}
