Leetcode 121.买股票的最佳时机
2024-09-01 07:16:27
题目描述:
给定一个数组,它的第 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。
用很容易想到的暴力解题法,这道题很简单就能做出来,就是两层嵌套循环找出差值最大的就行了。但我看力扣官方解答还有一种很妙的方法,一次遍历就能找到结果,算法很简单但就是不容易想到。
先上暴力解法的代码:(时间复杂度为O(n^2))
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;
}
}
力扣官方的一次遍历法:时间复杂度为O(n)
先假设给定的数组是{6,5,1,2,9,3}
画出图为:
先找到一个最小谷底(minprice),然后继续找最大的峰,这期间如果找到比之前低的谷,就更换minprice,然后再找最高的峰值,然后比较差值是否比之前的大,如果大就替换否则就继续寻找。
public class Pro{
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;
}
}
这道题的思想很棒,学到了。
最新文章
- oracle普通用户登录em
- 使用jspatch进行热修复的实战总结
- 基于mongodb的python之增删改查(CRUD)
- js问题
- CentOS安装wordpress权限问题
- 在where条件中使用CASE WHEN 语句
- javaweb学习总结(二十七)——jsp简单标签开发案例和打包
- git 用Gitk /usr/bin/which: no wish
- 网站常用css必备css reset
- JavaBean的一个小例子
- 什么是AOI自动光学检测机测试技术
- [置顶] 在js中如何实现方法重载?以及函数的参数问题
- 如何使用JS实现banner图滚动
- centos7 yum与Python3冲突
- JSON.NET的Self referencing loop detected with type的原因以及解决办法
- HTML+css基础认识
- 2028 ACM Lowest Common Multiple Plus
- canvas抛物线运动轨迹
- [No0000118]SQL Server附加数据库拒绝访问解决方法汇总
- RN-系列