算法:数组中的最大差值---“打擂台法“

这篇具有很好参考价值的文章主要介绍了算法:数组中的最大差值---“打擂台法“。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

文章来源:
https://blog.csdn.net/weixin_45630258/article/details/132737088
欢迎各位大佬指点、三连

1、题目:

给定一个整数数组 nums,找出给定数组中两个数字之间的最大差值。要求,第二个数字必须大于第一个数字。


2、分析特点:

  • 求最大差值 ==> 最大值 - 最小值
  • 只需要遍历价格数组一遍,记录历史最小值,非最小值的考虑是最大值。

3、代码:


4、复杂度分析:

  • 时间复杂度:O(n),只需要遍历一次。
  • 空间复杂度:O(1),只使用了常数个变量。

5、总结:

使用打擂台的思想,遍历的时候,考虑当前值是最小值,则记录最小值,否则考虑当前值是最大值,进行更新。


6、其他解法–暴力法

算法:数组中的最大差值---“打擂台法“,算法,算法,java,eclipse,intellij-idea,c++,c语言,c#


6-1、复杂度分析

算法:数组中的最大差值---“打擂台法“,算法,算法,java,eclipse,intellij-idea,c++,c语言,c#


7、题目变化

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

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

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

算法:数组中的最大差值---“打擂台法“,算法,算法,java,eclipse,intellij-idea,c++,c语言,c#

我们来假设自己来购买股票。随着时间的推移,每天我们都可以选择出售股票与否。那么,假设在第 i 天,如果我们要在今天卖股票,那么我们能赚多少钱呢?

显然,如果我们真的在买卖股票,我们肯定会想:如果我是在历史最低点买的股票就好了!太好了,在题目中,我们只要用一个变量记录一个历史最低价格 minprice,我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。

因此,我们只需要遍历价格数组一遍,记录历史最低点,然后在每一天考虑这么一个问题:如果我是在历史最低点买进的,那么我今天卖出能赚多少钱?当考虑完所有天数之时,我们就得到了最好的答案。


7-1、一次遍历
    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;
    }
■ 复杂度分析:
  • 时间复杂度:O(n),只需要遍历一次。
  • 空间复杂度:O(1),只使用了常数个变量。

7-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;
    }
}
■ 复杂度分析:

算法:数组中的最大差值---“打擂台法“,算法,算法,java,eclipse,intellij-idea,c++,c语言,c#




如果本文对你有帮助的话记得给一乐点个赞哦,感谢!文章来源地址https://www.toymoban.com/news/detail-703526.html

到了这里,关于算法:数组中的最大差值---“打擂台法“的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【华为OD机试】分割数组的最大差值【2023 B卷|100分】

    【 华为OD机试】-真题 !!点这里!! 【 华为OD机试】真题考点分类 !!点这里  !! 题目描述 给定一个由若干整数组成的数组nums ,可以在数组内的任意位置进行分割, 将该数组分割成两个非空子数组(即左数组和右数组),分别对子数组求和得到两个值, 计算这两个值的差值,

    2024年02月10日
    浏览(38)
  • 数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

    数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此

    2024年02月07日
    浏览(48)
  • nowcoder NC236题 最大差值

    目录 题目描述: 示例1 示例2 题干解析:  暴力求解: 代码展示:  优化: 代码展示:    题目跳转 https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204?tpId=128tqId=33768ru=/exam/oj   有一个长为 n 的数组 A ,求满足 0 ≤ a ≤ b n 的 A[b] - A[a] 的最大值。 给定数组 A 及它的大小 

    2024年02月10日
    浏览(33)
  • leetcode 2616. 最小化数对的最大差值

    在数组nums中找到p个数对,使差值绝对值的和最小。 思路: 最小差值应该是数值相近的一对数之间产生,让数值相近的数字尽量靠在一起方便计算,所以需要排序。 这里不去直接考虑一对对的数字,而是直接考虑差值的取值。 用binary search搜索一个差值。 左边界是0,右边界

    2024年02月13日
    浏览(36)
  • 215数组中的第K个最大元素

    给定整数数组 nums 和整数 k ,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 示例 2: 提示: 1 = k = nums.length = 105 -104 = nums[i] = 104 在这个代

    2024年02月22日
    浏览(35)
  • leetcode: 2789. 合并数组中的最大元素

    给你一个下标从 0 开始、由正整数组成的数组  nums  。 你可以在数组上执行下述操作 任意 次: 选中一个同时满足  0 = i nums.length - 1  和  nums[i] = nums[i + 1]  的整数  i  。将元素  nums[i + 1]  替换为  nums[i] + nums[i + 1]  ,并从数组中删除元素  nums[i]  。 返回你可以从最

    2024年03月14日
    浏览(36)
  • 215. 数组中的第K个最大元素

    给定整数数组 nums 和整数 k ,请返回数组中第 **k** 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 示例 2: 提示: 1 = k = nums.length = 105 -104 = nums[i] = 104 解答

    2024年02月11日
    浏览(40)
  • dp算法 力扣152乘积最大子数组

    本文是Java代码!! 152. 乘积最大子数组 - 力扣(LeetCode) 给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 示例 1: 输入

    2024年02月13日
    浏览(40)
  • 面试热题(数组中的第K个最大元素)

    给定整数数组  nums  和整数  k ,请返回数组中第  k  个最大的元素。 请注意,你需要找的是数组排序后的第  k  个最大的元素,而不是第  k  个不同的元素。        提到数组中最大元素,我们往往想到就是先给数组进行排序,然后取最大值,现在我们按照这个思路写一

    2024年02月13日
    浏览(51)
  • 2461. 长度为 K 子数组中的最大和

    2461. 长度为 K 子数组中的最大和 C代码:滑动窗口

    2024年02月10日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包