单调栈与单调队列

单调栈

PROBLEM

小C是个云南中医学院的大一新生，在某个星期二，他的高数老师扔给了他一个问题。

让他在1天的时间内给出答案。

但是小C不会这问题，现在他来请教你。

请你帮他解决这个问题。

有n个数，每个数有权值。

数学老师定义了区间价值为区间和乘上区间内的最小值。

现在要你找出有最大区间价值的区间是什么，并输出区间价值。

输入

每个输入文件只包含单组数据。
第一行一个整数n。(1 <= n <= 100000)
第二行n个整数a_1,a_2,...,a_n。(0 <= a_i <= 1000000)

输出

第一行输出一个整数，表示最大的区间价值。
第二行输出两个整数，表示区间的起点和终点。
保证答案唯一。

样例输入

6
10 1 9 4 5 9

样例输出

108
3 6

SOLUTION

单调栈可以求出每个点作为最小值时的有效区间。

与POJ2796撞题，网上可以找到很多解法，大多都是先找出每个点的最小值有效区间，然后根据区间用前缀和求区间和，再更新答案，这样的做法虽然时间复杂度是O(n)，但要循环多次，空间花销大，没有充分利用单调栈性质，不够优秀。

这个题（以下简称本题）其实可根据《算法竞赛进阶指南》0x11 单调栈例题 Largest Rectangle in a Histogram (POJ2559) 的解法修改而来。

我们可以对比这两个题，POJ2559（以下简称例题）题目大意是水平线上有若干矩形，求包含于这些矩形并集内部最大矩形的面积。（如下图所示）

实际上（最大）矩形面积可以转换为区间长度乘以区间最小值（的最大值）。

而本题则要求的是区间和乘以区间最小值。所以只要观察例题中区间长度是如何在维护单调栈过程中如何累积的，稍作修改便可以得到本题的代码。

而对于本题中求出具体区间的要求，我们可以发现在更新答案时，当前的枚举元素就是所在区间的右端点，而左端点则可以表示为右端点 - 有效区间长度 + 1 (闭区间) 。而区间长度怎么求的，就是例题所讨论的问题了。

CODE

#include <bits/stdc++.h>
 
using namespace std;
const int MAXN = 100005;
int a[MAXN],s[MAXN],len[MAXN]; // a[]:原始序列 s[]:栈（存放下标）len[]:栈中每个元素累积的有效区间长度
long long w[MAXN]; // w[]:栈中每个元素累积的有效区间和

int main() {
    long long ans = 0;
    int n,p = 0, l = 1, r = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= n + 1; i++) {
        if (a[i] > a[s[p]]) {
            s[++p] = i, w[p] = a[i], len[p] = 1; // 区间长度+1 区间和+a[i]
        } else {
            long long sum = 0;
            int dis = 0;
            while (a[s[p]] > a[i]) {
                sum += w[p]; // 累积区间和
                dis += len[p]; // 累积区间长度
                if (ans < sum * a[s[p]]) {
                    ans = sum * a[s[p]];
                    r = i - 1;
                    l = r - dis + 1; // 左端点 = 右端点 - 有效区间长度 + 1 (闭区间)
                }
                p--;
            }
            s[++p] = i, w[p] = sum + a[i], len[p] = dis + 1; // 区间长度+1 区间和+a[i]
        }
    }
    cout << ans << endl;
    cout << l << " " << r << endl;
    return 0;
}

单调队列

面试时碰到的，滑动窗口最小值问题。经典题目，网上可以搜一堆题解，就不贴代码了。

重点就是单调队列是双端队列，队列中存放下标。