#include <iostream> #include<vector> #include<algorithm> #include <stack> using namespace std; class Solution{ public: int maximalRectangle(vector<vector<char> >& matrix){ int m = matrix.size(),n = matrix[0].size(); vector<int> heights(n); int res = 0; for(int i = 0; i < m ; i++){ for(int j = 0; j < n;j++){ if(matrix[i][j] == '1') heights[j]++; else heights[j] = 0; } res = max(res,maxArea(heights)); } return res; } int maxArea(vector<int>& heights){ stack<int> stk; int res = 0; heights.push_back(-1); for(int i=0; i < heights.size(); i++){ while(!stk.empty() && heights[i] < heights[stk.top()]){ int idx = stk.top(); stk.pop(); int left = stk.empty()?-1:stk.top(); res =max(res,(i-left-1)*heights[idx]); } stk.push(i); } heights.pop_back( ); return res; } }; int main() { Solution solution; int m,n; cout<<"请输入矩形的行数和列数:"; cin>>m>>n; vector<vector<char> > matrix(m,vector<char>(n)); cout<<"请输入矩形元素(0或1):"<<endl; for(int i=0;i<m;i++){ for(int j=0;j<n;j++) { cin>>matrix[i][j]; } } int maxArea = solution.maximalRectangle(matrix); cout<<"矩形中最大的矩形面积是:"<<maxArea<<endl; return 0; }此代码用到了动态规划吗
时间: 2024-04-18 21:32:38 浏览: 11
这段代码没有直接使用动态规划。它使用了栈来解决最大矩形面积的问题。具体来说,它使用了单调栈算法来找到每个柱子的左右边界,然后计算出以该柱子为高度的矩形的面积。这个过程在循环中进行,每次计算出一个矩形的面积后与当前最大面积进行比较更新。因此,这个问题可以看作是在一维数组中找到最大矩形面积的问题,而不是动态规划。
相关问题
#include <iostream> #include <vector> #include <algorithm>
#include <iostream> 是C++中的一个头文件,它包含了输入输出流的相关函数和对象,例如cout和cin。通过包含这个头文件,我们可以在程序中使用标准输入输出流来进行输入和输出操作。
#include <vector> 是C++中的一个头文件,它定义了一个名为vector的容器类模板。vector是一个动态数组,可以存储不同类型的元素,并且可以根据需要动态调整大小。
#include <algorithm> 是C++中的一个头文件,它包含了一些常用的算法函数,例如排序、查找、替换等。通过包含这个头文件,我们可以在程序中使用这些算法函数来对容器中的元素进行操作。
#include<iostream> #include<cstdio> using namespace std;是什么意思
#include<iostream> #include<cstdio> using namespace std; 是C++中的预处理指令,用于引入头文件和命名空间。
1. #include<iostream> 是引入iostream头文件,其中包含了输入输出流的定义,例如cout和cin等。
2. #include<cstdio> 是引入cstdio头文件,其中包含了C语言标准输入输出函数的定义,例如printf和scanf等。
3. using namespace std; 是使用std命名空间,std是C++标准库的命名空间,其中包含了很多常用的函数和类。
这些预处理指令的作用是为了在程序中能够使用输入输出流和标准库函数,使得程序更加方便和简洁。