数组

大家好,我是老马。

今天我们一起来学习一下数组这种数据结构。

主要知识

数组需要拆分下面几个部分:

  1. 理论介绍

  2. 源码分析

  3. 数据结构实现?

  4. 题目练习(按照算法思想分类)

  5. 梳理对应的 sdk 包

  6. 应用实战

因为这个是 leetcode 系列,所以重点是 4、5(对4再一次总结)。

为了照顾没有基础的小伙伴,会简单介绍一下1的基础理论。

简单介绍1,重点为4。其他不是本系列的重点。

买卖股票系列

力扣 121. 买卖股票的最佳时机

力扣 122. 买卖股票的最佳时机 II

力扣 123. 买卖股票的最佳时机 III

【力扣 188. 买卖股票的最佳时机 IV

力扣 309. 买卖股票的最佳时机包含冷冻期

力扣 714. 买卖股票的最佳时机包含手续费

121. 买卖股票的最佳时机

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

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

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

示例 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。

提示:

1 <= prices.length <= 10^5 0 <= prices[i] <= 10^4

v1-贪心

思路

直接从后往前,找到最大的 maProfit 即可

实现

    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int n = prices.length;
        if(n <= 1) {
            return maxProfit;
        }

        int max = prices[n-1];        
        for(int i = n-2; i >= 0; i--) {
            int val = prices[i];
            
            // 挣到钱
            if(max > val) {
                maxProfit = Math.max(maxProfit, max-val);
            }

            // 更新未来最大值
            if(val > max) {
                max = val;
            }
        }

        return maxProfit;
    }

结果

1ms 击败 100.00%

反思

还是回顾一下这个系列吧,单个的题目还是不成体系。

全部靠能不能想到可不行。