CSP-201312-3-最大的矩形

解題思路

1. 遍歷所有可能的矩形高度：

• 通過遍歷所有矩形高度來找到最大的矩形，即對每個可能的高度 it（從直方圖中的最小高度到最大高度 heightMax），代碼將嘗試找到在這個高度或以上的最長連續條形段。這是通過再次遍歷直方圖中的所有條形實現的，這次是為了測量每個可能高度下的最長連續段。

2. 計算給定高度下的最大長度：

• 對于直方圖中的每個高度 it
  1. 初始化 lengthMax（給定高度下的最大長度）為-1和 length（當前連續段的長度）為0。
  2. 然后遍歷 heightArray，如果條形的高度大于或等于 it（jt >= it），length 加一（表示這個高度的連續段增加）。
  3. 如果條形的高度小于 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; vector<int>heightArray(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;
}