用c++解决以下问题不允许使用动态数组只允许使用静态数组：区间最小值最大时间限制：10s 内存限制：2560MB 代码提交间隔：3分钟现在可以提交 问题描述 给定一个长度为n的数列a你需要挑选一个长度为m的子区间使得这个区间内的最小值尽量大。输入格式 第一行包含两个整数n m分别表示数列长度和区间长度。第二行包含n个非负整数即数列a。输出格式 仅包含一个整数表示最大的最小值。样例输

可以使用滑动窗口来解决此问题。

首先，从左到右遍历数组a，记录当前窗口的最小值，并将这个最小值放入一个辅助数组minVal[]中。minVal[i]表示以a[i]为右端点的长度为m的子区间的最小值。

然后，从右到左遍历minVal[]数组，记录当前窗口的最大值，并将这个最大值放入一个辅助数组maxVal[]中。maxVal[i]表示以a[i]为左端点的长度为m的子区间的最大值。

最后，遍历maxVal[]数组，找到最小的最大值，即为所求的结果。

以下是使用C++实现的代码：

#include <iostream>
using namespace std;

const int MAXN = 100000;

int main() {
    int n, m;
    int a[MAXN], minVal[MAXN], maxVal[MAXN];

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 计算minVal[]
    int minIdx = 0;
    for (int i = 0; i < m; i++) {
        while (minIdx < i && a[i] <= a[minVal[minIdx]]) {
            minIdx++;
        }
        minVal[i] = i;
    }
    for (int i = m; i < n; i++) {
        while (minIdx < i && a[i] <= a[minVal[minIdx]]) {
            minIdx++;
        }
        minVal[i] = minVal[minIdx];
    }

    // 计算maxVal[]
    int maxIdx = n - 1;
    for (int i = n - 1; i >= n - m; i--) {
        while (maxIdx > i && a[i] >= a[maxVal[maxIdx]]) {
            maxIdx--;
        }
        maxVal[i] = i;
    }
    for (int i = n - m - 1; i >= 0; i--) {
        while (maxIdx > i && a[i] >= a[maxVal[maxIdx]]) {
            maxIdx--;
        }
        maxVal[i] = maxVal[maxIdx];
    }

    // 找到最小的最大值
    int ans = a[maxVal[0]];
    for (int i = 1; i <= n - m; i++) {
        ans = min(ans, a[maxVal[i]]);
    }

    cout << ans << endl;

    return 0;
}

该算法的时间复杂度为O(n)，空间复杂度为O(n)