題干：
?

眾所周知，IG是英雄聯(lián)盟S8世界總決賽冠軍，奪冠之夜，數(shù)億人為之歡呼！

賽后某百分百勝率退役ADC選手的某表情包意外走紅，某茍會(huì)長(zhǎng)看到此表情包也想模仿。

于是有n個(gè)友愛的萌新決定每人都送會(huì)長(zhǎng)一根長(zhǎng)為ai面包。(數(shù)據(jù)保證沒有面包的長(zhǎng)度相等)

會(huì)長(zhǎng)無(wú)聊時(shí)把面包擺成一排，他驚人地發(fā)現(xiàn)他喜歡這樣一類區(qū)間，區(qū)間[i, j]滿足條件：

區(qū)間里的面包沒有比左端點(diǎn)i號(hào)面包短的，同時(shí)也沒有比右端點(diǎn)j號(hào)面包長(zhǎng)的。

Gey會(huì)長(zhǎng)在思考這樣一個(gè)問題：
?

所有滿足條件的區(qū)間中j-i的最大值是多少？

輸入描述:

t組數(shù)據(jù)。

每組樣例第一行輸入整數(shù)n，接下來(lái)一行輸入n個(gè)正整數(shù)。

(t≤30, n≤1000, ai≤1000000)

輸出描述:

輸出滿足條件的區(qū)間中j-i的最大值。

示例1

輸入

復(fù)制

2 4 5 4 3 6 4 6 5 4 3

輸出

復(fù)制

1 0

解題報(bào)告：

? n=1e4其實(shí)可以直接暴力，不需要單調(diào)棧。。（當(dāng)做復(fù)習(xí)了）

? 但是最后還是枚舉的端點(diǎn)n^2了，，這題好像可以直接On的單調(diào)棧吧。。就跟那個(gè)暑假的題一樣的單調(diào)棧、、、抽空補(bǔ)了

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<stack> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int n; int a[MAX]; ll ans; int R[MAX]; int L[MAX]; stack<int> sk;//遞增棧 int main() {int t;cin>>t;while(t--) {cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i);//記錄左側(cè)第一個(gè)比它大的 while(!sk.empty()) sk.pop();for(int i = 1; i<=n; i++) {while(!sk.empty() && a[i] >= a[sk.top()] ) sk.pop();if(sk.empty()) L[i] = 0;else L[i] = sk.top();sk.push(i);}int ans = 0;for(int i = 1; i<=n; i++) {int minn = 0x3f3f3f3f,tar=L[i]+1;for(int j = L[i]+1; j<=i; j++) {if(a[j] <= minn) {tar=j;minn=a[j];}}ans = max(ans,i-tar);}// printf("%d %d\n",L[4],R[4]);printf("%d\n",ans);}return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的*【牛客 - 318B】签到题（单调栈，水题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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