題目鏈接：點(diǎn)擊查看

題目大意：給出一個長度為 n 的數(shù)列，現(xiàn)在規(guī)定對于任意長度區(qū)間為 len 的答案為，所有長度為 len 的區(qū)間內(nèi)的最小值的最大值，題目要求我們輸出len為 1 ~ n 時的答案

題目分析：看似很復(fù)雜，其實我們只需要維護(hù)每個區(qū)間內(nèi)的最小值就好了，并且順便維護(hù)一下區(qū)間長度，如果暴力枚舉每個區(qū)間顯然是不行的，我們可以利用單調(diào)棧，求出每個數(shù)字左邊和右邊第一個比他小的數(shù)字的位置，那么由這兩個位置組成的開區(qū)間內(nèi)的最小值顯然就是當(dāng)前數(shù)字了，有了區(qū)間的兩個端點(diǎn)區(qū)間長度也很容易計算了，O(n)計算出這些數(shù)據(jù)后，更新一下答案就好了，注意一下，因為并不是每個區(qū)間都能對應(yīng)上答案的，所以最后我們還需要根據(jù)答案數(shù)組再從大到小更新一遍，因為顯然如果 [ l , r ]的最小值為mmin，那么這段區(qū)間內(nèi)的任意一段連續(xù)的子區(qū)間的最小值肯定不可能小于 mmin，可以利用這個性質(zhì)更新沒有涉及到的答案區(qū)間

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;int a[N],L[N],R[N],ans[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i);stack<int>st;for(int i=1;i<=n;i++){while(st.size()&&a[st.top()]>=a[i])st.pop();if(st.size())L[i]=st.top();elseL[i]=0;st.push(i);}while(st.size())st.pop();for(int i=n;i>=1;i--){while(st.size()&&a[st.top()]>=a[i])st.pop();if(st.size())R[i]=st.top();elseR[i]=n+1;st.push(i);}memset(ans,0,sizeof(ans));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++)printf("%d ",ans[i]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 548D Mike and Feet(单调栈)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。