有一个长为 n 的数组 A ,求满足 0 ≤ a ≤ b < n 的 A[b] - A[a] 的最大值。
给定数组 A 及它的大小 n ,请返回最大差值。
数据范围: ,数组中的值满足
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; } };
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; } }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @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; }可惜运行超时
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; } };
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; } };
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; } }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @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
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 };
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; } }
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]
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 }
#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] ; } } } */
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
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 }
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; } };
单调栈比较适合该题,大于栈顶进栈,否则出栈至栈顶小于当前元素再进栈.最大值就在进栈和遍历结束的时候
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; }
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; } }