（转载）单调栈题目总结

题意：给出一个长度为n（n<100000）的序列，求出一个子序列，使得这个序列中的最小值乘以这个序列的和的值最大。

思路：枚举每一个点，然后算出以这个点为最小值的区间能向左向右扩展到哪里，然后选择最优的就行。

SOJ 3085: windy‘s cake V

题意：和POJ2796一样，只是不要求输出子序列的两个端点。

思路：粘贴上一题的代码就行

SOJ 3329: Maximum Submatrix II

题意：给出一个n*m的矩阵，求出这个矩阵的最大0矩阵的面积。

思路：枚举每一行，并且算出每一行中的0能向上生长过高，于是就得到了上面两题的模型，只是现在求得不是最小值乘以和，而是乘以序列长度。一次枚举，选择最优即可。

SOJ 2801: 正方形

题意：在一个n*n的矩阵中，有m个位置有障碍物，其他是空地，现在要求一个最大的正方形，使得正方形里面不含任何障碍物。

思路：只要把有障碍物的相应位置的值设为1，其他设为0。这样就可以得到上一题的模型。求法一样，只是在选择最优的时候是选择高度与区间长度中的较小值(题目求得是正方形的边长)。

SOJ 1773: Largest Rectangle in a Histogram

题目大意：给出一些宽度为1的墙的高度，现在要在墙上印刷广告，要求出一块面积最大的矩形。

思路：这个题是上面两题的弱化版，一维情况，所以只要扫描一遍就行了。