SPOJ - MINSUB——单调栈+01矩阵变换

本文主要是介绍SPOJ - MINSUB——单调栈+01矩阵变换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You are given an matrix M (consisting of nonnegative integers) and an integer K. For any submatrix of M’ of M define min(M’) to be the minimum value of all the entries of M’. Now your task is simple: find the maximum value of min(M’) where M’ is a submatrix of M of area at least K (where the area of a submatrix is equal to the number of rows times the number of columns it has).

Input
The first line contains a single integer T (T ≤ 10) denoting the number of test cases, T test cases follow. Each test case starts with a line containing three integers, R (R ≤ 1000), C (C ≤ 1000) and K (K ≤ R * C) which represent the number of rows, columns of the matrix and the parameter K. Then follow R lines each containing C nonnegative integers, representing the elements of the matrix M. Each element of M is ≤ 10^9

Output
For each test case output two integers: the maximum value of min(M’), where M’ is a submatrix of M of area at least K, and the maximum area of a submatrix which attains the maximum value of min(M’). Output a single space between the two integers.

Example
Input:
2
2 2 2
1 1
1 1
3 3 2
1 2 3
4 5 6
7 8 9

Output:
1 4
8 2
到现在为止还没有好好做过矩阵的单调栈，而且一上来就是一道比较可以的题目，也只能看看别人的题解
来做提了。
以前博客好像也写过，求最大的最小值或最小的最大值一般来说就是二分了，我们二分值的大小，然后将小于二分值的a数组里面的值赋为0，其他的赋为1，然后就是01矩阵求最大子矩阵的题目了。

#include<iostream>
#include<stack>
#include<cstdio>
#include<cstring>
using namespace std;
stack<int>st;
int a[1005][1005],f[1005][1005],r,c,k;
int check(int x)
{for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)f[i][j]=(a[i][j]>=x)?f[i-1][j]+1:0;int maxn=0;for(int i=1;i<=r;i++){while(!st.empty())st.pop();//将上次的值清除。for(int j=1;j<=c+1;j++){while(!st.empty()&&f[i][st.top()]>f[i][j]){int t=st.top();st.pop();if(st.empty())maxn=max(maxn,f[i][t]*(j-1));elsemaxn=max(maxn,f[i][t]*(j-1-st.top()));//刚开始一直不知道这是什么意思，自己调试了一下才发现
如果我们把j循环到c就停止了的话，那么如果两列的f是相同的，那就不会进入if语句，所以要变大一位。
然后这个j-1-st.top()就是列数，而f[i][t]就是之前的行数，因为是单调栈，
所以t肯定不比当前的行数大，看看能取到多少个列是有的情况，就是！st.empty()。}st.push(j);}}return maxn; 
}
int main()
{int t;scanf("%d",&t);while(t--){while(!st.empty())st.pop();memset(f,0,sizeof(f));int low=1e9,high=0,mid;scanf("%d%d%d",&r,&c,&k);for(int i=1;i<=r;i++)for(int j=1;j<=c;j++){scanf("%d",&a[i][j]);low=min(low,a[i][j]);high=max(high,a[i][j]);}int ans=0;while(high>=low){mid=low+high>>1;if(check(mid)>=k){low=mid+1;ans=mid;}elsehigh=mid-1;}printf("%d %d\n",ans,check(ans));}return 0;
}