萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

牛客NC7题-买卖股票的最好时机(一次交易)题解分析

发表于 2021-03-11 | 分类于 算法学习日记 | 0 | 阅读次数 408

题目描述

假设你有一个数组,其中第i个元素是股票在第i天的价格。
你有一次买入和卖出的机会。(只有买入了股票以后才能卖i出)。请你设计一个算法来计算可以获得的最大收益。

样例

  1. 示例1
    输入:[1,4,2]
    返回值:3

  2. 示例2
    输入:[2,4,1]
    返回值:2

题目评估

知识点:数组、动态规划
难度:简单

分析

本题我们可以用动态规划一次遍历,时间复杂度O(n)。
遍历的同时记录之前遍历过的数值中最小的股票值,并且每次i++时都计算当前的最大收益值和之前的最大收益值比对,如果本次最大,则记录保存。

Java代码题解

public class Solution {
    /**
     * @param prices int整型一维数组 
     * @return int整型
     */
       
    public int maxProfit (int[] prices) {
		int minbefore = Integer.MAX_VALUE;  // minbefore为遍历时i前面已经遍历过的股票中最低的值
        
		int maxprofit = Integer.MIN_VALUE;  // maxprofit为当前位置最大的收益
		
		for (int i = 0; i < prices.length; i++) {  // 一次遍历
			if(prices[i] < minbefore) {  // 首先判断当前股票值是否小于之前所有的股票值中最小的
				minbefore = prices[i];   // 如果是,将当前股票值赋值给minbefore
				
				if(prices[i] - minbefore > maxprofit) {  // 嵌套if语句计算当前为止的最大收益是否大于maxprofit
					maxprofit = prices[i] - minbefore;	 // 是则将其值赋值给maxprofit
				}
			} else {  // 这里的else语句是外层if语句的配对,如果当前股票值大于前边所有的最小值,执行下边的语句块
				if(prices[i] - minbefore > maxprofit) {  // 和上个if语句块一样,不给minbefore赋值,只是重新计算maxprofit,即当前最大收益
					maxprofit = prices[i] - minbefore;	 // 如果当前最大收益大于之前的最大收益,则给maxprofit赋值
				}
			}
			
		}
		
		return maxprofit;
    }
    
    
    public static void main(String[] args) {
    	Solution s = new Solution();
    	
    	int res = s.maxProfit(new int[]{1,4,2});
    	
    	System.out.println(res);
	}
}
牛客NC7题
# 算法 # 程序设计 # 动态规划
Spring学习笔记-AOP
MySQL所有的关联查询
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持