《LeetCode刷题》—121. 买卖股票的最佳时机

《LeetCode刷题》—121. 买卖股票的最佳时机

一、题目内容

原题连接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

题目：

二、个人答案（Java）

注意：该题个人答案未通过，运行时间超时

思路：相当于给一段数组，后面一个数减去前面一个数，求最大值，马上就想到了反向循环，循环两次，外循环每一个元素，内循环去循环前面的每一个数，求其最大值

代码：

class Solution {
    public int maxProfit(int[] prices) {
        int Max=0;
        for (int i = prices.length-1; i >=0; i--) {
            for (int j = i-1; j >=0 ; j--) {
                int temp=prices[i]-prices[j];
                if (temp>Max){
                    Max=temp;
                }
            }
        }
        return Max;
    }
}

三、官方答案（Java）

方法一：暴力法

代码：

public class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit) {
                    maxprofit = profit;
                }
            }
        }
        return maxprofit;
    }
}

方法二：一次遍历

思路：

代码：

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

官方答案来源：

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。