[刷题防痴呆] 0121 - 买卖股票的最佳时机 (Best T

题目地址

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

题目描述

121. Best Time to Buy and Sell Stock

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.

思路

for循环, 记录min和maxProfit.

关键点

• min起始为Integer.MAX_VALUE.
• profit起始为0.
• 可以记录两种状态, buy和sell, 要保证在buy和sell的时候自己手里的钱最多, 因为只能买卖一次, 所以每次buy都相当于从0开始.

代码

• 语言支持：Java

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        int min = Integer.MAX_VALUE;
        int profit = 0;
        
        for (int price : prices) {
            min = Math.min(price, min);
            profit = Math.max(profit, price - min);
        }
        
        return profit;
    }
}

// buy sell state
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int buy = Integer.MIN_VALUE;
        int sell = 0;
        for (int price: prices) {
            buy = Math.max(buy, 0 - price);
            sell = Math.max(sell, buy + price);
        }

        return sell;
    }
}