# 121. Best Time to Buy and Sell Stock 买卖股票的最佳时机

@TOC

[LeetCode]

Total Accepted: 98941 Total Submissions: 274449 Difficulty: Easy

## # 题目描述

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

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

Note that you cannot sell a stock before you buy one.

Example 1:

``````Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
``````

Example 2:

``````Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
``````

## # 解题方法

### # Java解法

1.保存在见到这个数值时，之前的所有值的最小值。 2.记录当前值与这个最小值的差。 3.找到在所有里边差值的最大值。

``````public class Solution {
public int maxProfit(int[] prices) {
if(prices.length<2) return 0;
int maxProfit=0;
int min=prices[0];
int cur=0;
for(int i=1;i<prices.length;i++){
cur=prices[i];
min=Math.min(min,cur);
maxProfit=Math.max(maxProfit,cur-min);
}
return maxProfit;
}
}
``````

AC:3ms

### # Python解法

``````class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices: return 0
N = len(prices)
mins = [0] * N
maxs = [0] * N
mins[0] = prices[0]
for i in range(1, N):
mins[i] = min(mins[i - 1], prices[i])
maxs[N - 1] = prices[N - 1]
for j in range(N - 2, -1, -1):
maxs[j] = max(maxs[j + 1], prices[j])
return max(maxs[i] - mins[i] for i in range(N))
``````

``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices: return 0
minPrice = float('inf')
profit = 0
for price in prices:
minPrice = min(minPrice, price)
profit = max(profit, price - minPrice)
return profit
``````

``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
N = len(prices)
res = 0
minP, maxP = float("inf"), 0
for i in range(N):
if minP > prices[i]:
minP = prices[i]
maxP = 0
if maxP < prices[i]:
maxP = prices[i]
res = max(res, maxP - minP)
return res
``````

### # C++ 解法

``````class Solution {
public:
int maxProfit(vector<int>& prices) {
int minP = INT_MAX;
int res = 0;
for (int p : prices) {
if (p < minP)
minP = p;
res = max(res, p - minP);
}
return res;
}
};
``````

## # 日期

2016/5/1 17:59:24 2018 年 4 月 10 号 2018 年 11 月 11 日 —— 剁手节快乐 2018 年 11 月 17 日 —— 美妙的周末，美丽的天气 2018 年 11 月 24 日 —— 周日开始！一周就过去了～ 2019 年 1 月 3 日 —— 2019年已经过去1%