题解：单调栈求解良好的感觉

题目描述

kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 $A_i$，$A_i$ 越大，表示人感觉越舒适。在一段时间 $\left[i,j\right]$ 内，人的舒适程度定义为 $\left[i,j\right]$ 中最不舒服的那一天的感受值 $\times$ $\left[i,j\right]$中每一天感受值的和。现在给出 kkk 在连续 $N$ 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？

输入格式

第一行为 $N$，代表数据记录的天数。

第二行 $N$ 个整数，代表每一天的感受值。

输出格式

一行，表示在最舒适的一段时间中的感受值。

样例 #1

样例输入 #1

6
3 1 6 4 5 2

样例输出 #1

60

提示

kkk 最开心的一段时间是第 $3$ 天到第 $5$ 天，开心值：$(6+4+5)\times 4=60$。

对于 $30\%$ 的数据，$1\le N\le 100$。

对于 $70\%$ 的数据，$1\le N\le 2000$。

对于 $100\%$ 的数据，$1\le N\le 100000$，$1\le \text{感受值}\le 1000000$。

单调栈

单调栈通常用于求解当前元素 $a[i]$ 往左或者往右第一个大于/小于 自身的数。

题目分析

这个题的区间是不定长的，因此如果要枚举所有区间，则需要 $O(n^2)$ 复杂度，再加上使用 $ST$ 表求区间最小值，则总的时间复杂度为 $O(n^{2}logn)$，看到 $n$ 的范围是 $n\le 10^5$，因此肯定会 $TLE$ 。

换位思考一下，即使区间有非常多，但是区间的最小值 仅可能是 $n$ 个，枚举数组 $a$，假设 $a[i]$ 为区间最小值，那如何让总的舒适程度更高呢？由于区间均为正数，因此基于贪心的思想，区间越长，区间和越大，舒适程度肯定越高，因此这个问题转为求解 以 $a[i]$ 为最小值的最长区间，然后计算舒适程度，求出最大舒适程度即可。

求以 $a[i]$ 为最小值的最长区间，暴力思路为：从 $a[i]$ 出发，向左一直找第一个小于 $a[i]$ 的数 $a[l]$，向右一直找第一个小于 $a[i]$ 的数 $a[r]$，因此以 $a[i]$ 为最小值的最长区间一定为 $a[l+1,...,r-1]$，利用前缀和求出区间和，再乘以区间最小值 $a[i]$ 即可得到以 $a[i]$ 作为最小值的最大舒适程度，然后枚举所有 $a[i]$，找出最大的舒适程度即可。

上面对于 $a[i]$ 往左右两边扩散找最小值的做法，可以借助单调栈进行优化，先从左往右遍历，下标入栈，维护栈单调递增，假设当前要入栈的元素为 $a[i]$，栈顶的元素为 $a[stk.top()]$，则如果 $a[i]<a[stk.top()]$，则栈顶元素往右边的第一个最小值一定为 $a[i]$，记录保存，由于要保证栈单调递增，因此栈顶出栈，继续判断新的栈顶，直到栈为空或者栈顶对应的元素小于 $a[i]$ 停止，此时 $a[i]$ 进栈；同理从右往左可以得到每个元素左边第一个小于自己的元素。

接下来只需要枚举数组中每个元素 $a[i]$，让 $a[i]$ 作为区间最小值，找到左右端点计算区间 最大舒适程度即可。

code

#include "bits/stdc++.h"
using namespace std;
const int N = 100000+7;
int n, lf[N], ri[N];
// lf[i]： 第 i 个元素往左第一个小于 a[i] 的元素下标
// ri[i]： 第 i 个元素往右第一个小于 a[i] 的元素下标
long long sum[N], a[N], ans = 0;
stack<int> stk;
// initLfRi函数：初始化lf数组和ri数组
void initLfRi() {
	for(int i=1; i<=n+1; i++) {  // 注意这里一定要到n+1, 否则ri数组不对，检测样例： 3 1 1 1 3
		while(!stk.empty() && a[i] < a[stk.top()]) {
			ri[stk.top()] = i;  // 栈顶元素右边第一个小于他的是 元素 a[i]
			stk.pop();
		}
		stk.push(i);   // 第i个元素进栈
    }
    while(!stk.empty()) stk.pop();   // 务必清空
    for(int i=n; i>0; i--) {    // 思考这里为什么可以不写 i>=0 ?
        while(!stk.empty() && a[i] < a[stk.top()]) { 
            lf[stk.top()] = i;  // 栈顶元素左边第一个小于他的是 元素 a[i]
            stk.pop();
        }
        stk.push(i);  // 第i个元素进栈
    }
	return ;
}
int main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];   // 初始化前缀和数组
    }
	initLfRi();
    for(int i=1; i<=n; i++) {  // 枚举最小值, 使得每个元素都做一次最小值
        ans = max(ans, (sum[ri[i]-1] - sum[lf[i]])*a[i]);  // 通过公式计算以 a[i] 为最小值的最长区间的舒适程度并更新最大值
    }
    cout << ans << endl;
    return 0;
}