c++找区间次大值问题！

时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 256MB，其他语言 512MB
出题人：
描述
给定一个长度为 n 的整数序列 a 1 ,a 2 ,…,a n ，请回答 q 次询问。对于每次询问，请找出区间 [l,r] 中的严格次大值。如果区间 [l,r] 中不存在严格次大值，输出 −1
记 a l,…,a r中最大的数为 m，那么区间 [l,r] 中的严格次大值定义为 a l ,…,a r中比 m 小的数中最大的一个

输入描述

第一行两个整数 n,q，表示序列的长度和询问的次数
第二行 n 个整数 a 1 ,a 2 ,…,a n，表示序列中的数
接下来 q 行，每行两个整数 l i ,r i，表示每次询问的区间的左右端点

输出描述

输出 q 行，每行一个整数，表示每次询问的答案
用例输入 1 
10 3
5 5 4 4 3 3 2 2 1 1
1 10
5 6
3 5
用例输出 1 
4
-1
3
提示

对于 100% 的测试数据，3≤n≤1000,1≤q≤1000,1≤a 
i≤1000000,1≤l i≤r i ≤n

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

int findSecondMax(vector<int>& nums, int l, int r) {
    int maxVal = nums[l];
    int secondMaxVal = -1;
    
    for (int i = l+1; i <= r; i++) {
        if (nums[i] > maxVal) {
            secondMaxVal = maxVal;
            maxVal = nums[i];
        } else if (nums[i] < maxVal) {
            secondMaxVal = max(secondMaxVal, nums[i]);
        }
    }
    
    return secondMaxVal;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        
        int result = findSecondMax(nums, l-1, r-1);
        cout << result << endl;
    }
    
    return 0;
}

这是一个demo，看看有没有帮助的

【以下回答由 GPT 生成】

思路解析

• 首先，读取输入的测试用例数量
• 对于每个测试用例，读取序列长度和询问次数
• 读取序列中的数
• 对于每次询问，找出区间 [l, r] 中的次大值
  • 首先，找出区间 [l, r] 中最大的数 m
  • 然后，遍历区间 [l, r]，找出比 m 小并且最大的数 s
  • 如果找不到 s，输出 -1，否则输出 s

代码实现

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

int main() {
    int numTestCases;
    cin >> numTestCases;

    while (numTestCases--) {
        int n, q;
        cin >> n >> q;
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        while (q--) {
            int l, r;
            cin >> l >> r;
            int m = *max_element(nums.begin() + l - 1, nums.begin() + r);
            int s = -1;
            for (int i = l - 1; i < r; i++) {
                if (nums[i] < m) {
                    s = max(s, nums[i]);
                }
            }
            cout << s << endl;
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度：对于每个测试用例，需要遍历序列找到最大值和次大值，时间复杂度为 O(n)，然后对于每个询问，需要遍历区间找到次大值，时间复杂度为 O(n)，所以整体的时间复杂度为 O(n * q)
• 空间复杂度：使用了一个大小为 n 的数组来保存输入的序列，所以空间复杂度为 O(n)

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7734188
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：C++指针取值！
• 您还可以看一下 陈小玉老师的C++快速入门课程中的 字符串小节, 巩固相关知识点
  
• 除此之外, 这篇博客: c++经典五道题中的 买钢笔 部分也许能够解决你的问题。