单调栈大水题
l[i] 表示 i 能扩展到的左边
r[i] 表示 i 能扩展到的右边
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define LL long long 4 5 const int MAXN = 2000002; 6 int n, t; 7 LL ans, a[MAXN], s[MAXN], l[MAXN], r[MAXN]; 8 9 inline int read() 10 { 11 int x = 0, f = 1; 12 char ch = getchar(); 13 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 14 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 15 return x * f; 16 } 17 18 inline LL max(LL x, LL y) 19 { 20 return x > y ? x : y; 21 } 22 23 int main() 24 { 25 int i; 26 n = read(); 27 for(i = 1; i <= n; i++) a[i] = read(); 28 a[0] = a[n + 1] = -1; 29 for(i = 1; i <= n + 1; i++) 30 { 31 while(t && a[s[t]] > a[i]) r[s[t--]] = i; 32 s[++t] = i; 33 } 34 t = 0; 35 for(i = n; i >= 0; i--) 36 { 37 while(t && a[s[t]] > a[i]) l[s[t--]] = i; 38 s[++t] = i; 39 } 40 for(i = 1; i <= n; i++) ans = max(ans, a[i] * (r[i] - l[i] - 1)); 41 printf("%lld ", ans); 42 return 0; 43 }