美文网首页
【LeetCode】卖卖股票的最佳时间I

【LeetCode】卖卖股票的最佳时间I

作者: 幽泉流霜 | 来源:发表于2019-10-24 21:54 被阅读0次

    只能交易一次。
    给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

    如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

    注意你不能在买入股票前卖出股票。

    示例 1:

    输入: [7,1,5,3,6,4]
    输出: 5
    解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
    示例 2:

    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

    1暴力法解决
    设置参数最大利润
    然后两次循环
    每次都算出利润来与最大利润比较
    如果有比它大的则替代。

    类似于求一个数组中的最大值或最小值的升级版本。

    总共循环n*(n+1)/2
    所以时间复杂度O(n2)
    空间复杂度O(1)

    package LeetCode_test;
    
    public class MaxProflit {
        public static void main(String[] args) {
    
        }
        public static 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 = prices[j]-prices[i];
                    }
                }
            }
            return maxprofit;
    
        }
    }
    
    

    2一次循环法

      public static int maxProfit(int[] prices) {
    
            int maxprofit = 0;
            int minprice = Integer.MAX_VALUE;
            for(int i = 0 ; i<prices.length ;i++){
                if(minprice>prices[i]){
    //如果比最小值小则替换
                    minprice = prices[i];
                }
                else if(maxprofit<prices[i]-minprice){
    //如果比最大利润大则替换
                    maxprofit = prices[i] - minprice;
                }
            }
            return maxprofit;
        }
    

    设立两个参数 最小值和最大利润
    每次刷新最小值并且比较出最大利润
    一次循环
    所以时间复杂度为 O(n)

    相关文章

      网友评论

          本文标题:【LeetCode】卖卖股票的最佳时间I

          本文链接:https://www.haomeiwen.com/subject/odkjyctx.html