121.买卖股票的最佳时机

• 题目描述
• 解题思路
• 代码实现

题目描述

解题思路

1. 两次遍历（i, j）价格数组，找出卖出和买入的最大差值（max(prices[j] - prices[i])）。
   i: 0 ~ prices.length - 2 ; i 只需遍历至数组的倒数第二个元素
   j: i + 1 ~ prices.length - 1
2. 一次遍历价格数组（i），每天更新当前历史最低点(minPrice)，更新当前最大利润（maxProfit = prices[i] - minPrices）。

代码实现

1. 思路1

public class Solution {
    public int maxProfit(int prices[]) {
        int maxProfit = 0;	//记录当前可以获得的最大利润
        int length = prices.length;		//获取价格数组长度
        for (int i = 0; i < length-1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] - prices[i]> maxProfit) {
                    maxProfit = prices[j] - prices[i];		//更新最大利润
                }
            }
        }
        return maxProfit;
    }
}

2. 思路2

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1){
            return 0;
        }
        int maxProfit = 0;
        int minPrice = prices[0];	//记录当前历史最低点
        for(int i=1; i<prices.length; i++){
            if(prices[i]<minPrice){
                minPrice = prices[i];	//更新历史最低点
            }else if(prices[i] - minPrice > maxProfit){
                maxProfit = prices[i] - minPrice;	//更新最大利润
            }
        }

        return maxProfit;
    }
}