ZeroJudge C907: 尋找最大矩形

現有 N 個寬度為 1 單位的長條圖 (例如下圖所示)，試求此長條圖中可以形成的最大矩形面積。

ZeroJudge C907 題目敘述

範例測資

範例輸入範例輸出
一筆測資，第一行輸入整數 N，接下來有 N 行，每行 1 個數字 H，依序代表每個長條圖的高度。(1 <= N、H <= 10000)輸出最大矩形面積
12
2
3
4
8
5
2
4
3
3
4
5
1		22

解題思路

使用 Map 來紀錄有出現的高度，然後跑一個 for (auto it:Map) 來判斷每一種高度的最大矩形面積，裡面再跑一個 For迴圈 從 0 到 N-1，並且在迴圈外設置一個變數 count 預設為 0，如果有中斷的情況，則要將 count 歸零，在歸零之前要計算 count*目前判斷的高度並判斷最大值。

範例程式碼－ZeroJudge C907: 尋找最大矩形

#include <iostream>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, num[20000] = {}, ans = -999;
    cin >> N;
    map<int, int>MAP;
    for (int i = 0; i<N; i++) {
        cin >> num[i];
        MAP[num[i]]++;
    }
    for (auto it:MAP) {
        const int height = it.first;
        int count = 0;
        for (int i = 0; i<N; i++) {
            if (num[i] < height) {
                ans = max(ans, count*height);
                count = 0;
                continue;
            }
            count++;
        }
        ans = max(ans, count*height);
    }
    cout << ans << "\n";
}

//ZeroJudge C907
//Dr. SeanXD
標籤

相關文章

發佈留言