网易笔试c++第三题题解

笔试时没做出来, 事后想了下用单调栈是可以做的

简要解释下题目, 给定一个长度n的数组, 分别有1到n长度的连续子序列, 每个子序列对应其包含最大值, 求每个长度的对应值中的最小值.
例如
5
4 2 3 5 7
对应值最小时分别取[2], [2,3], [4,2,3], [4,2,3,5], [4,2,3,5,7]
结果为
2 3 4 5 7
其中 n <= 100000
最容易想到的是简单的动态规划, n2会暴栈, 所以只用一阶矩阵
v[n]为输入数组
dp[i]表示当前位置下前i个位置中的最大值,
从后往前更新, 那么转移式为 dp[i] = max(dp[i - 1], v[i]), 即前i-1个位置的最大值和当前位置的值的大者
因为n很大, n2复杂度只能过60%, 然后就超时了..

这种连续区间最大最小的问题经常可以用单调栈来处理, 基本原理是访问到当前位置时, 更新以当前位置为右界的所有区间, 例如 6 4 5 7, 我们还是取区间最大值, 那么就用的递减单调栈, 栈内保存的是当前未确定以其为最大值的区间右界的已访问元素, 当访问到的值比栈顶大, 则它是栈中所有比它小的元素的区间右界, 而栈中元素左界是左侧比它大的第一个元素, 即它的前一个元素, 确定区间的元素则弹出栈,最终我们能得到以每个位置元素为区间最大值的所有情况.

回到题目, 我们要求1到n大小的区间对应值的最小值, 那么在确定一个位置元素的区间时, 可以更新所有不比它大的区间的最小值, 每个位置元素能对应的各个长度的区间都会被更新, 结果取小值即可. 复杂度分析有知道的可以帮忙分析下, 总之这种要低得多就是了..

代码不长, 自己看吧

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    vector<int> res(n + 1, INT_MAX);
    stack<pair<int, int>> s;
    s.emplace(INT_MAX, -1);
    s.emplace(v[0], 0);
    v.emplace_back(INT_MAX);
    for (int i = 1; i <= n; i++) {
        if (s.top().first < v[i]) {
            while (s.top().first < v[i]) {
                int val = s.top().first;
                s.pop();
                int len = i - 1 - s.top().second;
                for (int j = 1; j <= len; j++) {
                    res[j] = min(res[j], val);
                }
            }
        }
        s.emplace(v[i], i);
    }
    for (int i = 1; i <= n; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
}