解析网站dns,在线建站网站,wordpress插件吧,linuxvps建站教程CSP-201312-3-最大的矩形
解题思路
1. 遍历所有可能的矩形高度#xff1a;
通过遍历所有矩形高度来找到最大的矩形#xff0c;即对每个可能的高度 it#xff08;从直方图中的最小高度到最大高度 heightMax#xff09;#xff0c;代码将尝试找到在这个高度或以上的最长连…CSP-201312-3-最大的矩形
解题思路
1. 遍历所有可能的矩形高度
通过遍历所有矩形高度来找到最大的矩形即对每个可能的高度 it从直方图中的最小高度到最大高度 heightMax代码将尝试找到在这个高度或以上的最长连续条形段。这是通过再次遍历直方图中的所有条形实现的这次是为了测量每个可能高度下的最长连续段。
2. 计算给定高度下的最大长度
对于直方图中的每个高度 it 初始化 lengthMax给定高度下的最大长度为-1和 length当前连续段的长度为0。然后遍历 heightArray如果条形的高度大于或等于 itjt itlength 加一表示这个高度的连续段增加。如果条形的高度小于 it表示连续段结束则比较并更新 lengthMax如果当前连续段长度 length 大于之前记录的最大长度并重置 length 为0以开始新的长度测量。
3. 更新最大矩形面积
对于每个可能的高度 it代码计算可能的最大矩形面积it * lengthMax如果这个面积大于之前记录的最大面积 sMax则更新 sMax。
完整代码
#include iostream
#include algorithm
#include vector
using namespace std;int main() {int n, heightMax -1;cin n;long long sMax 0; vectorintheightArray(n); // 记录所有高度for (int i 0; i n; i){cin heightArray[i];heightMax max(heightMax, heightArray[i]); // 记录最大高度}heightArray.push_back(0); // 附终止条件for (const auto it : heightArray) // 遍历所有高度{int lengthMax -1, length 0;// 找到高度i下的最大长度for (const auto jt : heightArray) {if (jt it){length;}else{lengthMax max(length, lengthMax);length 0; // 重置}}long long s it * lengthMax;sMax max(sMax, s);}cout sMax;return 0;
}
