题解 | # B. Mike and Feet #

$[单调栈]$

这道题目可以当作结论来记住了

相当于用 $O(n)$ 的时间复杂度求：可以求出所有长度为 $k(1\leq k \leq n)$ 的连续子数组里最小值的最大值

首先如果所有长度为 $k$ 的最小值中的最大值为 $ans[k]$ ，那么一定满足 $ans[k - 1] \geq ans[k]$

我们可以求如果以当前 $a[i]$ 为最小值的最大区间，那么需要找到向左第一个小于 $a[i]$ 的值的位置 $l[i]$ ，向右第一个小于 $a[i]$ 的值的位置 $r[i]$ ，那么区间的长度为 $r[i] - l[i]- 1$ ，那么：

ans[r[i] - l[i] - 1] = max(ans[r[i] - l[i] - 1], a[i]);

这样找到最长的区间，对于长度小于 $r[i] - l[i]- 1$ 的区间的最大值一定大于等于 $ans[r[i] - l[i] - 1]$ ，所以我只需要求最长区间，最后：

for(int i = n - 1; i >= 1; i --) ans[i] = max(ans[i], ans[i + 1]);

如何求 $l[i]$ 与 $r[i]$ ，可以用单调栈的知识，栈里面存储的是下标：

for(int i = 1; i <= n; i ++){
        while(sta.size() && a[sta.top()] >= a[i]) sta.pop();
        if(sta.size()) l[i] = sta.top();
        else l[i] = 0;
        sta.push(i);
    }

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){

    int n; cin >> n;
    vector<int> a(n + 10), l(n + 10), r(n + 10), ans(n + 10);
    for(int i = 1; i <= n; i ++) cin >> a[i];   
    stack<int> sta;
    for(int i = 1; i <= n; i ++){
        while(sta.size() && a[sta.top()] >= a[i]) sta.pop();
        if(sta.size()) l[i] = sta.top();
        else l[i] = 0;
        sta.push(i);
    } 
    while(sta.size()) sta.pop();
    for(int i = n; i >= 1; i --){
        while(sta.size() && a[sta.top()] >= a[i]) sta.pop();
        if(sta.size()) r[i] = sta.top();
        else r[i] = n + 1;
        sta.push(i);
    } 
    for(int i = 1; i <= n; i ++){
        ans[r[i] - l[i] - 1] = max(ans[r[i] - l[i] - 1], a[i]);
    }
    for(int i = n - 1; i >= 1; i --) ans[i] = max(ans[i], ans[i + 1]);
    for(int i = 1; i <= n; i ++) cout << ans[i] << " ";
    cout << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

洛谷上：https://www.luogu.com.cn/problem/B4273

同样也是单调栈的使用，更加的直白，codeforce题目增加了思维

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){

    int n; cin >> n;
    vector<int> a(n + 10), l(n + 10), r(n + 10);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    stack<int> sta;
    for(int i = 1; i <= n; i ++){
        while(sta.size() && a[sta.top()] >= a[i]) sta.pop();
        if(sta.size()) l[i] = sta.top();
        else l[i] = 0;
        sta.push(i);
    }
    while(sta.size()) sta.pop();
    for(int i = n; i >= 1; i --){
        while(sta.size() && a[sta.top()] >= a[i]) sta.pop();
        if(sta.size()) r[i] = sta.top();
        else r[i] = n + 1;
        sta.push(i);
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        ans = max(ans, (r[i] - l[i] - 1) * a[i]);
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}