每日OJ_牛客_MT1最大差值_模拟+贪心_C++_Java

目录

牛客_MT1最大差值_模拟+贪心

题目解析

C++代码

Java代码

牛客_MT1最大差值_模拟+贪心

最大差值_牛客题霸_牛客网

描述：

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

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

数据范围： 2<n≤2∗10^5，数组中的值满足 0≤∣val∣≤5∗10^8

题目解析

遍历数组的过程中，使用一个变量标记一下当前位置之前所有元素的最小值即可。

C++代码

class Solution {
public:
    int getDis(vector<int>& A, int n) {
        // vector<int> arr(n, 0x3f3f3f3f); // 维护一个0到i的最小值
        // arr[0] = A[0];
        // int res = 0;
        // for(int i = 1; i < n; ++i)
        // {
        //     arr[i] = min(arr[i - 1], A[i]); // 可以用一个变量代替
        //     res = max(res, A[i] - arr[i]);
        // }
        // return res;

        int res = 0, prevMin = A[0];
        for(int i = 1; i < n; ++i)
        {
            prevMin = min(prevMin, A[i]);
            res = max(res, A[i] - prevMin);
        }
        return res;
    }
};

Java代码

import java.util.*;
public class Solution
{
    public int getDis (int[] arr, int n) 
    {
        int ret = 0;
        int minPrev = arr[0];
        for(int i = 1; i < n; i++)
        {
            minPrev = Math.min(minPrev, arr[i]);
            ret = Math.max(ret, arr[i] - minPrev);
        }
        return ret;
    }
}