LeetCode-84. 柱狀圖中最大的矩形(單調棧)

POJ-2559.Largest Rectangle in a Histogram

LeetCode-84. 柱狀圖中最大的矩形

Description

直方圖是由在公共基線處對齊的一系列矩形組成的多邊形。

矩形具有相等的寬度，但可以具有不同的高度。

例如，圖例左側顯示了由高度為2,1,4,5,1,3,3的矩形組成的直方圖，矩形的寬度都為1：

通常，直方圖用于表示離散分布，例如，文本中字元的頻率。

現在，請你計算在公共基線處對齊的直方圖中最大矩形的面積。

圖例右圖顯示了所描繪直方圖的最大對齊矩形。

Input

輸入包含幾個測試用例。

每個測試用例占據一行，用以描述一個直方圖，并以整數n開始，表示組成直方圖的矩形數目。

然後跟随n個整數h1，…，hn。這些數字以從左到右的順序表示直方圖的各個矩形的高度。

每個矩形的寬度為1。同行數字用空格隔開。

當輸入用例為n=0時，結束輸入，且該用例不用考慮。

資料範圍：

1 ≤ n ≤ 100000,

0 ≤ hi ≤ 1000000000

Output

對于每一個測試用例，輸出一個整數，代表指定直方圖中最大矩形的區域面積。

每個資料占一行。請注意，此矩形必須在公共基線處對齊。

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
           

Sample Output

8
4000
           

單調棧

我們可以維護一個單調遞增的棧，目前元素比棧頂元素大或等于則直接進棧，如果目前元素比棧頂元素小，則棧頂元素出棧，直到目前元素大于或等于棧頂元素，在出棧的過程中，記錄被彈出的寬度之和，并且每彈出一個矩形，就用它的高度乘上累計的寬度去更新答案。整個出棧過程結束後，把一個高度為目前矩形高度、寬度為累計值的新矩形入棧。

因為之前比它高度小的矩形都出棧了，是以需要累計比它小的寬度和。

整個掃描結束後，把棧中剩餘的矩形依次彈出，用同樣的方法，也可以增加一個高度為0的矩形，來避免在掃描結束後棧中有剩餘矩形。

LeetCode

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans=0;
        vector<int> w(heights.size()+1,1);
        vector<int> vec(heights);
        vec.push_back(0);
        stack<int> st;
        for(int i=0;i<vec.size();i++)
        {
            int width=0;
            while(!st.empty()&&vec[st.top()]>vec[i])
            {
                width+=w[st.top()];
                ans=max(ans,width*vec[st.top()]);
                st.pop();
            }
            st.push(i);
            w[i]=width+1;
        }
        return ans;
    }
};
           

Poj

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
long long ans = 0;
int a[100010];
int w[100010];
int n;
stack<int> st;
int main()
{
    while (cin >> n && n)
    {
        ans = 0;
        fill(w, w + n + 1, 1);
        while (!st.empty()) //棧清空
            st.pop();
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        a[n] = 0;
        for (int i = 0; i <= n; i++)
        {
            int width = 0; //記錄被彈出矩形的寬度和
            while (!st.empty() && a[st.top()] > a[i])
            {
                width += w[st.top()];
                ans = max(ans, (long long)a[st.top()] * width);
                st.pop();
            }
            w[i] = width + 1; //更新寬度
            st.push(i);
        }
        cout << ans << endl;
    }
    return 0;
}