#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; }这段代码用到了动态规划吗

是的，这段代码使用了动态规划来解决柱状图中最大矩形面积的问题。具体来说，它使用了两个动态规划数组 `dp1` 和 `dp2`，分别记录了每个柱子的左边界和右边界。通过从左到右和从右到左遍历柱子，更新这两个数组。然后，再遍历一次柱子，计算以当前柱子为高度的矩形面积，并与当前最大面积进行比较更新。因此，这个问题可以看作是动态规划的应用。