解题思路

这是一道求数组中满足条件的最大差值的问题，主要思路如下：

  1. 问题分析：

    • 给定长度为 的数组
    • 需要找到满足 的 的最大值
    • 即找到后面的数减去前面的数的最大差值

  2. 解决方案：

    • 维护一个数组 d 记录前 个数的最小值
    • 遍历数组，用当前值减去前面的最小值，更新最大差值

  3. 优化点：

    • 一次遍历计算前缀最小值
    • 一次遍历计算最大差值
    • 无需额外空间，可以原地修改

代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int getDis(vector<int>& A, int n) {
        if (n < 2) return 0;
        
        // 记录前i个数的最小值
        int minVal = A[0];
        // 记录最大差值
        int maxDiff = 0;
        
        // 遍历数组，更新最大差值
        for (int i = 1; i < n; i++) {
            maxDiff = max(maxDiff, A[i] - minVal);
            minVal = min(minVal, A[i]);
        }
        
        return maxDiff;
    }
};

import java.util.*;

public class Solution {
    public static int getDis(int[] A, int n) {
        if (n < 2) return 0;
        
        // 记录前i个数的最小值
        int minVal = A[0];
        // 记录最大差值
        int maxDiff = 0;
        
        // 遍历数组，更新最大差值
        for (int i = 1; i < n; i++) {
            maxDiff = Math.max(maxDiff, A[i] - minVal);
            minVal = Math.min(minVal, A[i]);
        }
        
        return maxDiff;
    }
}

class Solution:
    def getDis(self , A: List[int], n: int) -> int:
        if n < 2:
            return 0
        
        # 记录前i个数的最小值
        min_val = A[0]
        # 记录最大差值
        max_diff = 0
        
        # 遍历数组，更新最大差值
        for i in range(1, n):
            max_diff = max(max_diff, A[i] - min_val)
            min_val = min(min_val, A[i])
        
        return max_diff

算法及复杂度

  • 算法：一次遍历
  • 时间复杂度： - 只需要遍历一次数组
  • 空间复杂度： - 只需要常数额外空间