数组内两个元素的最大差

àì夳堔傛蜴生んèń 2022-08-09 14:54 126阅读 0赞

[Maximum difference between two elements such that larger element appears after the smaller number][]

2016京东商场校园招聘笔试题

**问题描述：**  
无序数组array, 找到数组中两个数的最大差值, 且大数出现在小数之后，如：arr\[i\]-arr\[j\], 且 i<j  
比如： array 是 \[2, 3, 10, 6, 4, 8, 1\]，最大差值是8（2-10）

**方法1**  
依次访问数组中的每一个元素：

1) 记录当前访问过的数组中的最小值 min_val;
    2) 当前元素值arr[i] - min_val 和 max_diff作比较
       若大于 max_diff , 则更新它的值

时间复杂度O(n)  
空间复杂度O(1)

#include <iostream>
    
    using namespace std;
    
    int maxDiff(int *arr, int n)
    {
            int min_val = arr[0];
            int max_diff = arr[1]-arr[0];
            for(int i=1; i<n; ++i)
            {
                    if(max_diff <(arr[i]-min_val))
                            max_diff = arr[i] - min_val;
                    min_val = arr[i]<min_val?arr[i]:min_val;
            }
            return max_diff;
    }
    
    
    int main()
    {
            int arr[] = {
       2, 3, 10, 6, 4,8,1};
            cout<<maxDiff(arr, 7)<<endl;
    }

[Maximum difference between two elements such that larger element appears after the smaller number]: http://www.geeksforgeeks.org/maximum-difference-between-two-elements/

发表评论取消回复

表情：

评论列表（有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python计算两个数组差的绝对值

Python计算两个数组差的绝对值在Python中，计算两个数组差的绝对值可以使用numpy库中的abs函数。实现这个过程需要先将两个数组转换成numpy数组，然后调用ab

￡神魔★判官ぃ/ 2024年03月26日 21:44/ 0 赞/ 78 阅读

相关 215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1: > 输入: \[3,2,1,5,6

朱雀/ 2023年02月23日 08:27/ 0 赞/ 142 阅读

相关 LeetCode 1464. 数组中两元素的最大乘积

给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums\[i\]-1)\(nums\[j\]-1) 取得最大值。请你计算并返回该式的最大值。

谁借莪１个温暖的怀抱￠/ 2023年01月06日 15:57/ 0 赞/ 114 阅读

相关【leetcode.1464】数组中两元素的最大乘积

一、题目描述给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums\[i\]-1)\(nums\[j\]-1) 取得最大值。请你计算并返

矫情吗；*/ 2022年12月09日 04:50/ 0 赞/ 127 阅读

相关 215. 数组中的第K个最大元素

题目在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1: > 输入: \[3,2

悠悠/ 2022年11月21日 03:42/ 0 赞/ 161 阅读

相关 215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1: 输入: \[3,2,1,5,6,4

谁践踏了优雅/ 2022年11月19日 11:13/ 0 赞/ 158 阅读

相关 1913. 两个数对之间的最大乘积差

[https://leetcode-cn.com/problems/maximum-product-difference-between-two-pairs/][https_l

ゞ浴缸里的玫瑰/ 2022年09月06日 01:16/ 0 赞/ 137 阅读

相关数组内两个元素的最大差

[Maximum difference between two elements such that larger element appears after the smal

àì夳堔傛蜴生んèń/ 2022年08月09日 14:54/ 0 赞/ 127 阅读

相关 215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。输入: \[3,2,3,1,2,4,5,5,6\

╰+攻爆jí腚メ/ 2022年05月08日 08:08/ 0 赞/ 195 阅读

相关求数组两个元素与(&)运算最大值，异或(^)运算最大值

摘要：本文首先解决的是数组中两元素与运算最大值问题，之后拓展异或运算最大值问题。建议读者顺序阅读，比较两问的相同与不同。 -------------------- 问题

古城微笑少年丶/ 2022年03月01日 09:18/ 0 赞/ 427 阅读