首页 > 试题广场 >

最大差值

[编程题]最大差值
  • 热度指数：11908 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

有一个长为 n 的数组 A ，求满足 0 ≤ a ≤ b < n 的 A[b] - A[a] 的最大值。

给定数组 A 及它的大小 n ，请返回最大差值。


数据范围： ，数组中的值满足
示例1

输入

[5,1],2

输出

0
示例2

输入

[5,6],2

输出

1
算法知识视频讲解
添加回答
C++
牛客472102317号头像 牛客472102317号 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param n int整型 
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        // write code here
        int min_pos=0,res=0;
        for(int i=0;i<n;i++){
            if(A[i]<=A[min_pos])
                min_pos=i;
            else
                res=max(res,A[i]-A[min_pos]);
        }
        return res;
    }
};

发表于 2021-12-01 18:18:56 回复(0)
Java
马老师的金轮头像 马老师的金轮 
 public int getDis (int[] A, int n) {
        // write code here
        int max = 0;
        int maxNum = Integer.MIN_VALUE;
        for(int i=n-1;i>=0;i--){
            if(A[i] > maxNum){
                maxNum = A[i];
            }
            if(maxNum - A[i] > max){
                max = maxNum - A[i];
            }
        }
        return max;
    }

发表于 2022-02-22 18:31:57 回复(0)
Java
pein531头像 pein531

算法流程

使用预处理技巧，构建两个与原数组相同的辅助数组left和right：
  1. left[i]表示包括A[i]在内的，及其左边所有元素中的最小值；
  2. right[i]表示包括A[i]在内的，及其右边所有元素中的最大值。
然后遍历0~n，计算right[i]-left[i]的最大值即可 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型一维数组 
     * @param n int整型 
     * @return int整型
     */
    public int getDis (int[] A, int n) {
        // write code here
        int[] left = new int[n], right = new int[n];
        left[0] = A[0];
        right[n - 1] = A[n - 1];
        for(int i = 1; i < n; i++){
            left[i] = Math.min(left[i - 1], A[i]);
            right[n - 1 - i] = Math.max(A[n - 1 - i], right[n - i]);
        }
        int maxDiff = 0;
        for(int i = 0; i < n; i++){
            maxDiff = Math.max(maxDiff, right[i] - left[i]);
        }
        return maxDiff;
    }
}

复杂度分析

left数组和right数组可以通过遍历一遍求得，时间复杂度为O(n)。然后求最大差值再遍历一遍，时间复杂度为O(n)，算法整体的复杂度还是O(n)。而开辟了两个辅助数组的空间，空间复杂度为O(n)。
发表于 2021-12-15 14:29:27 回复(0)
牛客665672417号头像 牛客665672417号 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A int整型一维数组 
 * @param ALen int A数组长度
 * @param n int整型 
 * @return int整型
 */
int getDis(int* A, int ALen, int n ) {
    // write code here
    int max=0;
    int sum=0;
    for(int i=0;i<ALen;i++)
    {
        for(int j=0;j<i;j++)
        {
            sum=0;
            sum=A[i]-A[j];
            if(sum>max)
            {
                max=sum;
            }
        }
    }
    return max;
}
可惜运行超时
发表于 2022-09-17 16:51:35 回复(0)
布加迪.威龙头像 布加迪.威龙 
static const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}
();

class Solution {
  public:
    int getDis(vector<int>& A, int n) {
        int d[n];
        d[0] = A[0];
        int r = 0;
        for (int i = 1; i < n; ++i) {
            if (A[i] < d[i - 1])
                d[i] = A[i];
            else d[i] = d[i - 1];
        }
        for (int i = 1; i < n; ++i) {
            if (A[i] - d[i] > r)
                r = A[i] - d[i];
        }
        return r;
    }
};

发表于 2022-07-19 09:10:25 回复(0)
C++
牛客嗷嗷头像 牛客嗷嗷 
class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param n int整型 
     * @return int整型
     */
    int getDis(vector<int> &A, int n)
    {
        // write code here
        int max = 0, min = A[0];
        for (int i = 1; i < n; i++)
        {
            if (min > A[i])
            {
                min = A[i];
                continue;
            }
            int t = A[i] - min;
            max = (max > t ? max : t);
        }
        return max;
    }
};

发表于 2022-01-28 17:17:46 回复(0)
Java
啊哈哈h头像 啊哈哈h 
import java.util.*;
public class Solution {
    public int getDis (int[] A, int n) {
        int min = A[0];
        int[] dp = new int[n];
        dp[0] = A[0];
        int res = 0;
        for(int i = 1; i < n; i++){
            min = Math.min(min, A[i]);
            dp[i] = A[i] - min;
            res = Math.max(dp[i], res);
        }
        return res;
    }
}

发表于 2021-12-01 13:18:00 回复(0)
Python3
liangzhengjie头像 liangzhengjie
不断更新最小值，遇到比最小值大则取一次值就好了 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A int整型一维数组 
# @param n int整型 
# @return int整型
#
class Solution:
    def getDis(self , A: List[int], n: int) -> int:
        # write code here
        dp = [0 for i in range(n)]
        min_num = A[0]
    
        res = 0
        for i in range(1, n):
            min_num = min(min_num, A[i-1])

            if A[i] > min_num:
                res = max(res, A[i]- min_num)

        return res



编辑于 2024-03-19 22:38:53 回复(0)
贪吃的小鱼干蚌埠住了头像 贪吃的小鱼干蚌埠住了
最后也只能通过30个样例
int getDis(int* A, int ALen, int n ) {
    // write code here
    long long int min=A[0];
    long long int max=0;
    int i=0;
    int j=0;
    for(i=0;i<ALen-1;i++)
    {
        for(j=i;j<ALen;j++)
        {
            if((A[j]-A[i])>max)
            {
                max=(A[j]-A[i]);
            }
        }
    }
    return max;
}

发表于 2023-12-08 23:56:31 回复(0)
在刷代码的芝士很聪明头像 在刷代码的芝士很聪明 
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A int整型vector
     * @param n int整型
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        int k = A[0], max = 0;
        for (int i = 1; i < n; i++) {
            k = min(A[i], k);
            int p = A[i] - k;
            if (p > max)max = p;
        }
        return max;
    }  // write code here
};

发表于 2023-08-28 11:35:41 回复(0)
牛客931188754号头像 牛客931188754号
class Solution:
    def getDis(self , A: List[int], n: int) -> int:
        # write code here
        min=A[0]
        max=A[0]
        req = 0
        minindex = 0
        maxindex = 0
        for i in range(n):
            if A[i] > max:
                max = A[i]
                maxindex = i
            if A[i] < min:
                if req < max - min:
                    req = max - min
                max = A[i]
                maxindex = i
                min = A[i]
                minindex = i
        if maxindex > minindex:
            if req < A[maxindex] - A[minindex]:
                req = A[maxindex] - A[minindex]
        return req
发表于 2023-05-27 14:13:13 回复(1)
Java
梁山教父头像 梁山教父 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型一维数组 
     * @param n int整型 
     * @return int整型
     */
    public int getDis (int[] A, int n) {
        // write code here
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            min=Math.min(A[i],min);
            if(A[i]-min>max){
                max=A[i]-min;
            }
        }
        return max;
    }
}

发表于 2023-05-18 15:39:06 回复(0)
Python3
danspace头像 danspace 
class Solution:
    def getDis(self , A: List[int], n: int) -> int:
        # write code here
        # dp[i]为到i点的最优解
        dp = [0]*n
        cur_min = A[0]
        for i in range(1, n):
            cur_min = min(cur_min, A[i])
            if A[i] <= A[i-1]:
                dp[i] = dp[i-1]
            else:
                dp[i] = max(dp[i-1], A[i] - cur_min)
        return dp[-1]

发表于 2023-04-27 13:53:48 回复(0)
牛客693279660号头像 牛客693279660号 
func getDis(A []int, n int) int {
	// write code here
    //递归思想，类似动态规划
    //A[:n]最大差值 = Biggest{ A[n-1]-Smallest(A[:n]) , A[:n-1]最大差值 }
	results := 0        
	preSmallest := A[0] 
	for i := 1; i < n; i++ {
		v1 := A[i] - preSmallest
		v2 := results
		if v1 >= v2 {
			results = v1
		} else {
			results = v2
		}
		if preSmallest > A[i] {
			preSmallest = A[i]
		}
	}
	return results
}


发表于 2023-04-26 19:26:59 回复(0)
C++
hacks头像 hacks
用贪心过的
更新最小被减数和差值最大。 
#include <climits>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A int整型vector
     * @param n int整型
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        // write code here
        // 这个题目注意 要满足
        // 索引 b >=a   样例1 A[1]-A[0] =-4 ,A[1]-A[1] = 0

       // 找一个最小的被减数
       int cur = A[0] ; 
       int maxx = INT_MIN ; 
       for(int i = 0;i<n ; i++) {
            int diff = A[i] -cur ; 
            // 更新被减数
            // 在0-i
            cur = min (cur ,A[i]) ; 
            
            maxx = max(maxx,diff) ; 
       }
       return maxx ; 
    }
};
// [2676 4662 8383 357 6595 ] 5
// 6238
/**
 int maxx = INT_MIN ;
        // 枚举b
        for (int i = 0 ; i < n ; i++ ) {
            // 枚举a
            for (int j = 0 ; j < n ; j++ ) {
                if (A[i] - A[j] > maxx && i >=j) {
                    maxx = A[i] - A[j] ;
                }
            }


        }

*/


发表于 2023-03-23 23:59:04 回复(0)
在写日记的大师兄很想喝咖啡头像 在写日记的大师兄很想喝咖啡 
class Solution:
    def getDis(self , A: List[int], n: int) -> int:
        ans = 0
        min = A[0]
        for i in A:
            if i < min:
                min = i
            if i - min > ans:
                ans = i - min
        return ans

发表于 2023-03-19 18:23:29 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A int整型一维数组 
 * @param n int整型 
 * @return int整型
*/
func getDis( A []int ,  n int ) int {
    ans:=0
    min:=A[0]
    for i:=1;i<n;i++{
        if A[i]<min{
            min=A[i]
        }
        if A[i]-min>ans{
            ans=A[i]-min
        }
    }
    return ans
}

发表于 2023-03-06 21:21:33 回复(0)
C++
池中物_2024头像 池中物_2024 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param n int整型 
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        // write code here
        int min_num = A[0], res = 0;
        for(int i = 1; i < n; i++){
            min_num = min(min_num, A[i]);
            res = max(res, A[i] - min_num);
        }
        return res;
    }
};

发表于 2023-01-08 13:38:24 回复(0)
JavaScript Node
几号发货头像 几号发货

单调栈比较适合该题,大于栈顶进栈,否则出栈至栈顶小于当前元素再进栈.最大值就在进栈和遍历结束的时候

function getDis(A, n) {
    if (n <= 1) return 0;
    let stack = [];
    let max = 0;
    for (let i = 0; i < n; i++) {
        if (!stack.length) {
            stack.push(A[i]);
        } else {
            if (stack[stack.length - 1] < A[i]) {
                max = Math.max(max, A[i] - stack[0]);
            } else {
                while (stack.length) {
                    if (stack[stack.length - 1] >= A[i]) {
                        stack.pop();
                    } else {
                        break;
                    }
                }
            }
            stack.push(A[i]);
        }
    }
    if (stack.length) {
        max = Math.max(max, stack[stack.length - 1] - stack[0]);
    }
    return max;
}
发表于 2022-11-14 14:14:33 回复(0)
爱睡觉的杨大爷头像 爱睡觉的杨大爷 
import java.util.*;


public class Solution {
   //可以实现时间复杂度为O(N) ，空间复杂度为O(1)
    //从左到右遍历一次，每遍历一个数，比较记录下数组中最小的数，然后拿记录的最大差值与当前数减去前面记录的最小数
    //比较，记录下最大差值。这个思路巧妙在，max=A[b]-A[a],b>=a，所以不会有错解漏解的存在
    public int getDis (int[] A, int n) {
        int max=0;
        int min=A[0];
        for(int i=1;i<n;i++){
            min=Math.min(min,A[i]); //先对min进行更新
            max=Math.max(max,A[i]-min);  //接着对max进行更新
        }
        return max;
    }
}

发表于 2022-08-09 11:04:09 回复(0)
提交观点

问题信息

贪心 动态规划 模拟
难度：
38条回答 2989浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号