输入一个m * n的二维矩阵,求最大滑动子方阵的最大值的均值?
vector<vector<int>> matrix {{2,5,2,1,3}, {3,4,1,3,4}, {2,7,5,2,6}, {5,7,8,0,9}, {1,5,7,8,3}, {2,8,4,5,6}};
vector<vector<int>> matrix {{2,5,2,1,3,2}, {3,4,1,3,4,8}, {2,7,5,2,6,4}, {5,7,8,0,9,5}, {1,5,7,8,3,6}};
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
// vector<vector<int>> matrix {{2,5,2,1,3,2}, {3,4,1,3,4,8}, {2,7,5,2,6,4}, {5,7,8,0,9,5}, {1,5,7,8,3,6}};
vector<vector<int>> matrix {{2,5,2,1,3}, {3,4,1,3,4}, {2,7,5,2,6}, {5,7,8,0,9}, {1,5,7,8,3}, {2,8,4,5,6}};
int main()
{
vector<int> temp;
vector<vector<int>> max_num;
int m=matrix.size();
int n= matrix[0].size();
vector<vector<int>> matrix_rev(matrix[0].size(), vector<int>());
if(m>n)
{
for (int i = 0; i < matrix.size(); i++)
for (int j = 0; j < matrix[0].size(); j++)
matrix_rev[j].push_back(matrix[i][j]); // 二维vector转置
for(int i=0;i<n;i++)
{
deque<int> q;
temp.clear();
for(int j=0;j< m;j++)
{
while(q.size() && q.back() < matrix_rev[i][j])
q.pop_back();
q.push_back(matrix_rev[i][j]);
if(j-n>=1 && q.front() == matrix_rev[i][j-n])
q.pop_front();
if(j>=n-1)
temp.push_back(q.front());
}
q.clear();
max_num.push_back(temp);
}
}
else
{
for(int i=0;i<m;i++)
{
deque<int> q;
temp.clear();
for(int j=0;j< n;j++)
{
while(q.size() && q.back() < matrix[i][j])
q.pop_back();
q.push_back(matrix[i][j]);
if(j-m>=1 && q.front() == matrix[i][j-m])
q.pop_front();
if(j>=m-1)
temp.push_back(q.front());
}
q.clear();
max_num.push_back(temp);
}
}
int sum=0,max_ans, cnt=0;
// cout<<max_num[0].size()<<endl;
for(int i=0;i<max_num[0].size();i++)
{
max_ans=0;
for(int j=0;j< max_num.size();j++)
{
if(max_ans<max_num[j][i])
max_ans=max_num[j][i];
}
sum +=max_ans;
cnt++;
}
cout<< float(sum)/cnt<<endl;
return 0;
}
应用了y总的滑动窗口单调队列的知识,但是在本题中显得很蠢,算法小白,求教大佬们的做法。