萤火小屋

优律的知识库

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

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

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

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

题目描述

假设你有一个数组,其中第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所有的关联查询
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

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