給定一組非負整數組成的數組h，代表一組柱狀圖的高度，其中每個柱子的寬度都為1。 在這組柱狀圖中找到能組成的最大矩形的面積（如圖所示）。 入參h為一個整型數組，代表每個柱子的高度，返回面積的值。 這個問題和前面我們講過的一個盛最多水的容器很相似，不同的地方是這個邊界可以不為首尾，因為內部也可能存在更大面積的矩形，而那個題目要求以兩個邊界為前提，組成的容器。上次我準備用dp來解決，沒有成功，那是因為原理不符，沒有最優子結構。這個問題就可以用dp來解決了。 首先我們來看，存在最優子結構，如果目前存在最大的矩形的面積，再加一個柱子，我們可以判斷出加上它，最大的矩形面積。然后這個子問題也是重疊的，在加不加新柱子的問題上，我們判斷最大矩形面積的方法是一樣的，唯一不同的是邊界不同，也就對應的參數不同。另外問題的邊界也存在，就是我們輸入的這幾個高度。子問題的求解也是獨立的。 int main() {int n;cin >> n;vector<long> h(n+1);for (int i = 1; i <= n; i++)cin >> h[i];vector<vector<long>> dp(n+1, vector<long>(n+1));for (int i = 1; i <= n; i++)dp[i][i] = h[i];int min_h;// for (int i = n-1; i >= 1; i--)// {//for (int j = i; j <= n; j++)// {// min_h = h[i];// for (int k = i; k <= j; k++)// min_h = min_h < h[k] ? min_h : h[k];// dp[i][j] = (min_h *(j - i + 1)) > dp[i][j - 1] ? (min_h *(j - i + 1)) : dp[i][j - 1];// dp[j][i] = dp[i][j] = dp[i][j] > dp[i + 1][j] ? dp[i][j] : dp[i + 1][j];// }// }for (int j = 1; j<=n; j++){for (int i = j-1; i >= 1; i--){min_h = h[i];for (int k = i; k <= j; k++)min_h = min_h < h[k] ? min_h : h[k]; dp[i][j] = (min_h *(j - i + 1)) > dp[i][j - 1] ? (min_h *(j - i + 1)) : dp[i][j - 1];dp[j][i] = dp[i][j] = dp[i][j] > dp[i + 1][j] ? dp[i][j] : dp[i + 1][j];}}for(int i=0;i<=n;i++){cout << dp[1][i] << '\0';}return 0; }

這里面，dp[i][j]代表從i到j的最大矩形面積。首先dp[i][i]就是該高度下的單個矩形面積。我們需要存儲從i到j的最小高度，因為多加一個柱狀圖，我們需要判斷以最小高度為高的矩形面積，比原來的最大矩形面積相比的結果。我們需要通過比較dp[i][j-1]和dp[i+1][j]以及新計算的面積三個來得到dp[i][j]。程序中加黑字體中，第一行將dp[i][j-1]和新面積相比，將最大值賦給了dp[i][j]，但是這并不是最終的結果，因為如果dp[i+1][j]中的面積要大于這兩個，我們就會漏掉。所以第二行也很必要。一定不能丟。

上述的過程不好理解的話，就理解下邊界情況，如果就兩個直方圖，我們需要比較這兩個單獨的面積以及兩個并在一起的面積，必須比較完這三個才能得到最大的面積。

（2）其實這道題還可以用單調棧來做，具體做法見上一篇《單調棧以及應用》，這里不再贅述。

轉載于:https://www.cnblogs.com/mini-coconut/p/9108434.html

總結

以上是生活随笔為你收集整理的美团笔试最大矩形面积的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。