目录
牛客_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;}
}