解题思路

这是一道数组处理问题，主要思路如下：

  1. 问题分析：

    • 给定一个递增序列
    • 需要删除一个中间元素(不包括首尾)
    • 求删除后序列的最大间隔的最小可能值
    • 最大间隔定义为相邻元素的最大差值

  2. 解决方案：

    • 遍历每个可以删除的位置
    • 计算删除每个元素后的最大间隔
    • 在所有可能的最大间隔中取最小值
    • 注意处理边界情况

  3. 优化实现：

    • 只需要考虑删除点及其相邻位置的间隔变化
    • 其他位置的间隔不会受到影响
    • 维护全局的最小值

代码

#include <iostream>
using namespace std;

const int MAXN = 101;
int arr[MAXN];

int main() {
    int n;
    while (cin >> n) {
        // 读入数据
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        
        // 计算原始最大间隔
        int maxGap = -1001;
        for (int i = 0; i < n-1; i++) {
            maxGap = max(maxGap, arr[i+1] - arr[i]);
        }
        
        // 尝试删除每个中间元素
        int ans = 1001;
        for (int i = 1; i < n-1; i++) {
            // 计算删除i后的新间隔
            int newGap = arr[i+1] - arr[i-1];
            // 更新答案
            int curMax = max(maxGap, newGap);
            ans = min(ans, curMax);
        }
        
        cout << ans << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            
            // 读入数据
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            
            // 计算原始最大间隔
            int maxGap = -1001;
            for (int i = 0; i < n-1; i++) {
                maxGap = Math.max(maxGap, arr[i+1] - arr[i]);
            }
            
            // 尝试删除每个中间元素
            int ans = 1001;
            for (int i = 1; i < n-1; i++) {
                // 计算删除i后的新间隔
                int newGap = arr[i+1] - arr[i-1];
                // 更新答案
                int curMax = Math.max(maxGap, newGap);
                ans = Math.min(ans, curMax);
            }
            
            System.out.println(ans);
        }
        sc.close();
    }
}

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 计算原始最大间隔
    max_gap = max(arr[i+1] - arr[i] for i in range(n-1))
    
    # 尝试删除每个中间元素
    ans = float('inf')
    for i in range(1, n-1):
        # 计算删除i后的新间隔
        new_gap = arr[i+1] - arr[i-1]
        # 更新答案
        cur_max = max(max_gap, new_gap)
        ans = min(ans, cur_max)
    
    return ans

def main():
    while True:
        try:
            print(solve())
        except EOFError:
            break

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：遍历 + 贪心
  • 时间复杂度： - 为序列长度
  • 空间复杂度： - 只需要常数额外空间