您好,欢迎来到花图问答。
搜索
您的当前位置:首页LeetCode 121. Best Time to Buy a

LeetCode 121. Best Time to Buy a

来源:花图问答

题目

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。
样例
给出一个数组样例 [3,2,3,1,2], 返回 1

Solution

Approach #1 (Brute Force) 暴力搜索

思路很简单,我们就要找出数组中,差值最大的两个数,要求是前一个数小,后一个数大,那么遍历两边即可,找出所有这样的差值,找出其中最大的一个

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;
    }

Approach #2 (One Pass) Greedy 贪婪法

通过一遍遍历,找出到此为止之前最小的min,并与当前的值求差,保存最大的差值,遍历完,最后的差值即是最大差值。

Paste_Image.png
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;
    }

Copyright © 2019- huatuowenda.com 版权所有 湘ICP备2023022495号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务