LeetCode150道面试经典题-买卖股票的最佳时机(简单)

简介: 数组 prices[]表示一个股市一段时间的价格,prices[i] 表示股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

 

1、题目

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0


2、示例

示例1:

输入:[7,1,5,3,6,4]

输出:5

解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例2:

输入:prices = [7,6,4,3,1]

输出:0

解释:在这种情况下, 没有交易完成, 所以最大利润为 0。



3、解题思路

该题有两种解决方法:

1.暴力法:

通过遍历取出数组中的每一个元素,并跟剩下的元素进行求差的结果再与最大利润进行比较,如此循环找出最大利润值。

2.动态规划法(优解):

首先假设第i天是获取最大的利益值,那么购入时候肯定是在集合[0,i-1]的范围里面找到其中的最小值,然后两者的价格相减就是我们要的最大利益。


4、LeetCode代码与案例代码

1.暴力法

LeetCode代码:

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++){
                if (prices[j] - prices[i]>maxProfit){
                    maxProfit = prices[j] - prices[i];
                }
            }
        }
        return maxProfit;
    }
}

image.gif

案例代码:

package LettCode05;
public class javaDemo {
    public static void main(String[] args) {
        int nums[] =new int[]{7,6,4,3,1};
//        暴力解法
        int maxProfit = 0;
        for (int i=0;i< nums.length-1;i++){
            for (int j=i+1;j< nums.length;j++){
                if (nums[j] - nums[i]>maxProfit){
                    maxProfit = nums[j] - nums[i];
                }
            }
        }
        System.out.println("最大利润为"+maxProfit);
    }
}

image.gif

image.gif编辑

总结:时间复杂度为O(n^2),空间复杂度为O(1);

2.动态规划法

LeetCode代码:

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

image.gif

案例代码:

package LeetCode06;
public class javaDemo {
    public static void main(String[] args) {
        int prices[] = new int[]{7,1,5,3,6,4};
//        动态规划
        int max_profit = 0;
        int lowPrice = Integer.MAX_VALUE;
        for (int i=0;i<prices.length;i++){
//            找到第i天前的最小值
            if (prices[i]<lowPrice){
                lowPrice = prices[i];
//                某天的值减去这天前的最小值就是这天的最大利益
//                通过比较每一天的利益大小得到最大利益
            }else if (prices[i]-lowPrice>max_profit){
                max_profit = prices[i]-lowPrice;
            }
        }
        System.out.println("最大利润为"+max_profit);
    }
}

image.gif

image.gif编辑

总结:该方法的时间复杂度为O(n),空间复杂度为O(1)

目录
相关文章
|
4月前
|
算法 Python
【Leetcode刷题Python】309. 最佳买卖股票时机含冷冻期
解决LeetCode上309题“最佳买卖股票时机含冷冻期”的Python代码示例,利用动态规划方法计算在含有冷冻期约束下的最大利润。
45 1
|
4月前
|
算法 Python
【Leetcode刷题Python】121. 买卖股票的最佳时机
解决LeetCode上121题“买卖股票的最佳时机”的Python代码示例,采用一次遍历的方式寻找最佳买卖时机以获得最大利润。
64 1
|
4月前
|
算法
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
66 0
|
4月前
|
算法 Python
【Leetcode刷题Python】714. 买卖股票的最佳时机含手续费
提供了两种解决买卖股票最佳时机含手续费问题的Python实现方法:贪心算法和动态规划算法。
50 0
|
4月前
|
算法 Python
【Leetcode刷题Python】122.买卖股票的最佳时机 II
LeetCode "买卖股票的最佳时机 II" 问题的Python代码实现,采用贪心算法在股票价格上升的每一天买入并卖出,以获得最大利润。
25 0
|
5月前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
5月前
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
|
算法
leetcode题解:121.买卖股票的最佳时机
leetcode题解:121.买卖股票的最佳时机
44 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行