POJ.2559[leetcode.84]直方图最大矩形及二维情况

LeetCode Hard 84 . Largest Rectangle in Histogram
POJ 2559 Largest Rectangle in a Histogram | N=10W
GDUFE OJ 1181 | N=5000
给出一个直方图，求里面的最大矩形面积，如下图面积为10。

最简单粗暴的办法是对于每个方块，我们求出它向左和向右能延伸的最远距离，再乘以它的自身高度就行了。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define clr( a , x ) memset ( a , x , sizeof (a) );
#define RE freopen("1.in","r",stdin);
const int maxn = 1005;

int largestRectangleArea(int* heights, int heightsSize) {
    int dis[maxn];
    clr(dis,0);
    int ans = 0;
    for (int i = 0; i < heightsSize; i++) {
        for (int j = i + 1; j < heightsSize; j++) {
            if ( heights[i] <= heights[j]) dis[i]++;
            else break;
        }
        for (int j = i; j >= 0; j--) {
            if ( heights[i] <= heights[j]) dis[i]++;
            else break;
        }
        dis[i] = heights[i] * dis[i];
        if (dis[i] > ans) ans = dis[i];
    }
    return ans;
}
int main()
{
    // RE
    int heights[maxn];
    int n;
    while ( scanf("%d", &n)!=EOF ) {
        for (int i = 0; i < n; i++)
            scanf("%d", &heights[i]);
        printf("%d
", largestRectangleArea(heights, n));
    }
    return 0;
}

然而 POJ 2559 n=10W 平方级别得超时。
下面不再考虑极/最大矩形的中间点，考虑矩形的区间端点。
我们知道 4，5，6，3 这种递增的数据我们不需要计算全部情况，只需要计算4跟3组成端点的情况。所以同理，每个柱子都只能向右延伸到某个高度小于他的柱子。

维护一个单调递增的栈，栈里存放已遍历过的柱子编号（意味着栈里元素是递增的）
我们遍历当前柱子当作区间右端点，只要栈顶编号对应的柱子高于当前柱子，我们就弹出且计算一次面积（取两次栈顶的位置作宽度【不能取栈顶元素否则无法覆盖左边，有这种case: 2 1 2 答案是3】，栈顶对应的柱高作为高度），这个面积代表以栈顶元素的柱高能向右边延伸到当前点（不含当前点）。

然后为了避开最开始栈为空的特判，我们在所有矩形前插入个0且入栈一个0（小于min{矩形宽}的数字）；为了让最后个矩形也能被计算，我们在矩形后也插入个0。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define clr( a , x ) memset ( a , x , sizeof (a) );
#define RE freopen("1.in","r",stdin);
const int maxn = 100000 + 5;
int h[maxn];

int main() {
    int n;
    while (scanf("%d",&n)!=EOF,n) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d",&h[i]);
        }
        stack<int>s;
        ll ans = 0;
        s.push(0);
        h[0] = 0;
        h[++n] = 0;
        for (int i = 1; i <= n; ++i) {
            while (h[i] < h[s.top()]) {
                ll height = h[s.top()];s.pop();
                ll width = i - s.top() - 1; //这里的top是经过pop的
                if (width * height > ans) {
                    ans = width * height;
                }
            }
            s.push(i);
        }
        cout << ans << endl;
    }
    return 0;
}

对应LeetCode Hard 84 . Largest Rectangle in Histogram的版本

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if(n==0) return 0;
        int ans = 0;

        stack<int>s;
        s.push(0);
        heights.insert(heights.begin(),-1);

        heights.push_back(0);
        n++;
        for (int i = 1; i <= n; ++i) {
            while (heights[i] < heights[s.top()]) {
                int a = heights[s.top()];s.pop();
                int b = i - s.top() - 1;
                if (a * b > ans) {
                    ans = a * b;
                }
            }
            s.push(i);
        }
        return ans;
    }
};

POJ 3494 Largest Submatrix of All 1’s | 二维
给一个二维的01矩形，求最多1所围成的矩形面积。

0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

我们把二维转为一维，如图我们从最后行看的话等价于

0 2 2 0

这就成一维了，再进一步，我们需要在每行都这么干，然后就ok了。
先对每行的每列求出该列之上1的个数（如上），遍历每一行，按一维的情况去处理就行了。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
#define clr( a , x ) memset ( a , x , sizeof (a) );
#define RE freopen("1.in","r",stdin);
const int maxn = 2005;

int n,m;
int arr[maxn][maxn],data[maxn][maxn];
int solve(int row){
    stack<int>s;
    int ans = 0;
    s.push(0);
    data[row][0] = 0;
    data[row][m+1] = 0;
    for (int j = 1; j <= m+1; ++j) {
        while (data[row][j] < data[row][s.top()]) {
            int a = data[row][s.top()]; s.pop();
            int b = j - s.top() - 1;
            if (a * b > ans) {
                ans = a * b;
            }
        }
        s.push(j);
    }
    return ans;
}
int main() {

    // RE
    while (scanf("%d%d",&n,&m)!=EOF) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j){
                scanf("%d",&arr[i][j]);
            }
        }
        clr(data,0);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j){
                if(arr[i][j]) data[i][j] = arr[i][j] + data[i-1][j];
                else   data[i][j] = 0;
            }
        }
        int ans =  0;
        for (int i = 1; i <= n; ++i){
            ans = max(ans,solve(i));
        }
        printf("%d
", ans);
    }
    return 0;
}