POJ-2559 Largest Rectangle in a Histogram

Posted on | Edited on | In | Views:

题意

45660aba95464e61adfbbcc7cea2c44c

求柱形图中的最大矩形面积。

题解

法一: 求每个点左边连续比它大的最左边的下标，保存在 $l[]$ 数组里,求每个点右边连续比它大的最右边的下标，保存在 $r[]$ 数组里

法二: 维护一个单调栈, 如果 $h$ 大于栈顶元素，则入栈, 否则，将栈内元素出栈，直到满足上面的条件。出栈时，我们要将出栈元素对之后问题的影响全部考虑进行处理，才能保证做法的正确性。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <ctime>
#define ull unsigned long long
#define ll long long
#define inf 0x3f3f3f3f
#define mod (int)1e9+7
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forn(i, n) for (int i = n; i >= 0; i--)
#define mem0(a) memset(a, 0, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define meminf(a) memset(a, inf, sizeof(a))
using namespace std;

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n,tmp;
  while (cin>>n&&n) {
    ll ans=0;
    vector<pair<int, int> >sta;//点的权值 权值大于等于该点的数量
    for0(i, n){
      cin>>tmp;
      int count=0;
      forn(i, sta.size()-1){
        if (sta[i].first>tmp) {
          count+=sta[i].second;
          ans=max(ans, (ll)sta[i].first*count);
          sta.pop_back();
        }else break;
      }
      sta.push_back(pair<int, int>(tmp,count+1));
    }
    int count=0;
    forn(i, sta.size()-1){
      count+=sta[i].second;
      ans=max(ans, (ll)sta[i].first*count);
    }
    cout<<ans<<endl;
  }
  return 0;
}