例题

例题1 SP1805 Largest Rectangle in a Histogram

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

一句话题意：求一个最大子矩阵

看到这个问题，我们应该先在脑内想一些特殊且简单的模型，然后推广到更一般的情况。比如，如果所有矩形都一样高会怎样，显然，答案就是整个矩阵。那么，如果矩形高度是单调的又会怎样呢？同样的，找到一个矩形的高，显然此时子矩阵的高已经被限制住了。那么它现在要做的就是尽量往左，右扩展。这样就能使得高一样的情况下宽尽量大。然后尝试每一个这样的矩形的高就可以了。

既然这样，矩形高度并不单调的时候，我们又应该怎么办呢？回顾之前的过程，我们得到一个新的矩形的高的时候，都会将它往左右扩展到边界。那么矩形高度并不单调的时候就会出现如下情形：

显然，被灰色矩形截下来的上面凸出的部分已经没用了。因为后面的矩形即便是高度增加到很高，扩展边界时也不可能越过波谷达到这块凸出的地方了。因此，我们直接将它们扔掉！继续这样下去。为了实现这一想法，我们可以建立一个栈，里面存储我们找到的矩形，而且要时刻保持栈中矩形的高度单调递增，这样就可以应用我们之前设想的单调递增模型来解决最大面积问题。这种经典算法被称作单调栈。

详细一点来说，我们需要进行这样的操作：

当我们遇到一个新的矩形的时候，

1. 这个矩形比栈顶矩形更高。

那么我们将它直接入栈，不违反我们的单调递增原则

2. 这个矩形比栈顶矩形更矮

正如上图的情况，我们遇到一个比上一个矩形矮的矩形。那么我们可以丢掉“凸出来的那一部分”。怎么丢掉呢？那就是只留下它们的宽度（因为宽度对新矩形的面积有贡献），然后用他们的宽度乘上它们的高度来更新答案，然后丢掉它们的高度（因为对新矩形没贡献）。

从操作上看来，它表现为将所有大于当前矩形高度的矩形累加并储存起来，然后更新答案并将它们退掉，将这个宽度加在当前矩形上，使得它成为一个有它自己高度和前面退掉的矩形的宽度的新矩形，然后将它存到栈中，仍然不影响单调递增原则。这样O(n)遍历一次，就可以得到一个高度单调递增，宽度不尽相同的矩阵栈。然后将这些矩形弹出，用相同的方法更新答案，注意，最好增加一个高度为0的矩形a[n+1]，以免剩余矩形弹出不干净。

练习题

例二 P1169 [ZJOI2007]棋盘制作

题目描述

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8×8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。

而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。

小Q找到了一张由N×M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。

不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。

于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？

输入格式

包含两个整数NN和MM，分别表示矩形纸片的长和宽。接下来的N行包含一个N×M的01矩阵，表示这张矩形纸片的颜色（0表示白色，1表示黑色）。

输出格式

包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。

问题分析

这道题要求我们找出满足任意相邻格子颜色不同的最大正方形和最大矩形。我们将这个问题的第一问使用了DP而非单调栈，所以我们重点回顾第二问：

• 怎么求最大矩形

还记得例一吗，例一给出了一个序列，我们将一维的序列的数字看作高度，将它“提起来”变成二维。这个题上来就是二维，看似与例一不同，其实是例一的“变种”。我们先来考虑前i行，对于每个格子，它上面都有一些另外的格子，但是颜色不一定是如何的。然而我们需要求黑白相间的最大面积，那么我们可以从每一个元素向上扩展出黑白相间的高度，这样这个问题就瞬间变成了例一。
我们只需要从每一行向上扩展出高度，然后就可以建立单调栈求解了！当然也要注意同一行相邻格子的颜色哦。

关键代码

    for (int j = 1; j <= m; ++j) {
        for (int i = 1; i <= n; ++i) {//为了降低时间复杂度,采用按列递推的方式 
            line[i][j].col = b[i][j];//记录当前点的颜色 
            line[i][j].h = 1;//初始化高度 
            if (b[i][j] == b[i - 1][j])//如果和上一行颜色不同 
                line[i][j].h = line[i - 1][j].h + 1;//直接继承上一列的长度 
        }//否则就保持长度为1. 
    }
    for (int bot = 1; bot <= n; ++bot) {//bot即bottom,也就是我们建立单调栈的一行 
        int flag = -1;
        for (int i = 1; i <= m; ++i) {//扫描这一行 
            if (s[top] < line[bot][i].h && (flag == -1 || flag == line[bot][i].col)) {//如果这一格向上高度更高 
                s[++top] = line[bot][i].h, w[top] = 1;//直接入栈,记录宽度为1 
                flag = line[bot][i].col;//记录栈顶颜色(也就是注意同一行的相邻格子之间的颜色 
            }
            else {//如果遇到高度低的 
                int totwide = 0;//记录弹出总宽度 
                while (top > 0 && (s[top] > line[bot][i].h || flag != line[bot][i].col)) {//栈非空且矮或与栈顶颜色不同 
                    totwide += w[top];//累加宽度 
                    ans2 = max(ans2, (long long)totwide * s[top]);//更新答案 
                    top--;//退栈 
                }
                s[++top] = line[bot][i].h;//将新形成的具有自己的高度和累加的宽度的新矩形加入栈中. 
                if (flag == line[bot][i].col)//如果颜色相同,代表新矩形可以替代原来处于栈顶的矩形. 
                    w[top] = totwide + 1;//可以累加宽度 
                else w[top] = 1;//否则只能作为新的起点 
                flag = line[bot][i].col;//记录栈顶颜色. 
            }
        }
        if (top > 0) {//这一行扫完了,退栈 
            int totwide = 0;
            while (top > 0) {
                totwide += w[top];//累加宽度 
                ans2 = max(ans2, (long long)totwide * s[top]);//更新答案 
                top--;//退栈 
            }
        } 
    }
    cout << ans2 << endl;

这样问题就解决啦！
欢迎批评和指正！