#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: int largestRectangleArea(vector<int>& heights) { int n = heights.size(); if(!n) return 0; int res = heights[0]; vector<int>dp1(n,-1); vector<int>dp2(n,n); for(int i = 1; i < n; ++i) //从左到右遍历每个柱子 { int left = i-1; while(left>=0 && heights[left]>=heights[i]) { left = dp1[left]; } dp1[i] = left; } for(int i = n-2; i>=0; --i) //从右到左遍历每个柱子 { int right = i+1; while(right<n && heights[right]>=heights[i]) { right = dp2[right]; } dp2[i] = right; } for(int i = 0; i < n; ++i) //计算以当前柱子为高度的矩形面积 { int width = (dp2[i]-1)-(dp1[i]+1)+1; res = max(res,heights[i]*width); } return res; } }; int main() { Solution solution; int n; cout << "请输入柱状图的数量: "; cin >> n; vector<int> heights(n); cout << "请输入每个柱状图的高:\n"; for (int i = 0; i < n; i++) { cin >> heights[i]; } int maxArea = solution.largestRectangleArea(heights); cout << "柱状图中最大的矩形面积是: " << maxArea << endl; return 0; }这段代码用到了动态规划吗
时间: 2024-04-18 21:32:38 浏览: 11
是的,这段代码使用了动态规划来解决柱状图中最大矩形面积的问题。具体来说,它使用了两个动态规划数组 `dp1` 和 `dp2`,分别记录了每个柱子的左边界和右边界。通过从左到右和从右到左遍历柱子,更新这两个数组。然后,再遍历一次柱子,计算以当前柱子为高度的矩形面积,并与当前最大面积进行比较更新。因此,这个问题可以看作是动态规划的应用。
相关问题
#include <iostream> #include<algorithm> #include<cmath> #include <queue> using namespace std;
#include <iostream>:这是C++标准库中的头文件,用于输入输出流操作,包括cin、cout等。
#include<algorithm>:这是C++标准库中的头文件,用于提供各种算法操作,如排序、查找等。
#include<cmath>:这是C++标准库中的头文件,用于提供数学函数操作,如绝对值、平方根等。
#include <queue>:这是C++标准库中的头文件,用于提供队列操作,包括入队、出队等。
using namespace std;:这是C++的命名空间声明,表示使用std命名空间,可以直接使用std中的函数和对象。
#include<iostream> #include<stack> #include<queue>
这是C++的头文件引用,分别包含了输入输出流、栈和队列的类。其中iostream头文件定义了输入输出流的类,stack头文件定义了栈的类,queue头文件定义了队列的类。以下是它们的简单使用示例:
1. iostream头文件的使用:
```c++
#include<iostream>
using namespace std;
int main() {
int num;
cin >> num; // 从控制台读取一个整数
cout << "You entered " << num << endl; // 输出读取到的整数
return 0;
}
```
2. stack头文件的使用:
```c++
#include<iostream>
#include<stack>
using namespace std;
int main() {
stack<int> s; // 定义一个int类型的栈
s.push(1); // 压入元素1
s.push(2); // 压入元素2
s.push(3); // 压入元素3
while (!s.empty()) { // 遍历栈中元素
cout << s.top() << " "; // 输出栈顶元素
s.pop(); // 弹出栈顶元素
}
return 0;
}
```
3. queue头文件的使用:
```c++
#include<iostream>
#include<queue>
using namespace std;
int main() {
queue<int> q; // 定义一个int类型的队列
q.push(1); // 入队1
q.push(2); // 入队2
q.push(3); // 入队3
while (!q.empty()) { // 遍历队列中元素
cout << q.front() << " "; // 输出队首元素
q.pop(); // 弹出队首元素
}
return 0;
}
```
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)