HDU - 1506 - 히 스 토 그램 에서 가장 큰 사각형 - 알고리즘 노트

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1506
Problem Description：
Input：
The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, …, hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.
Output：
For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.
Sample Input：
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
Sample Output：
8 4000
주요 사고: 모든 최소 단위 길이 의 사각형 이 높 기 때문에 (즉 입력 한 배열 값) 이 위치 가 가장 왼쪽, 가장 오른쪽 으로 확장 할 수 있 는 아래 표 시 된 최대 값 만 계산 하면 됩 니 다.마지막 으로 모든 데 이 터 를 옮 겨 다 니 며 가장 오른쪽, 가장 왼쪽 값 을 최대 사각형 의 길 이 를 줄 이 고 대응 하 는 높이 를 곱 하면 현재 데이터 가 얻 은 최대 사각형 면적 이 며 가장 큰 면적 을 찾 으 면 된다.코드 에 대해 한번 계산 해 보면 알 수 있다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

#define ll long long
#define clean(arrays) memset(arrays, 0, sizeof(arrays))

ll a[100005], lefts[100005], rights[100005];        // lefts   rights          
ll max_area;

int main()
{
    int n, t;
    while (cin>>n, n != 0)
    {
        clean(a);   clean(lefts);    clean(rights);
        for (int i = 1; i <= n; i++)
            cin>>a[i];

        lefts[1] = 1;   //          ，   
        rights[n] = n;

        //  a[i]       a[i]          ，   lefts  
        for (int i = 1; i <= n; i++)
        {
            t = i;
            while (t > 1 && a[i] <= a[t-1])  t = lefts[t - 1];      //      t - 1      
            lefts[i] = t;
        }

        //  a[i]       a[i]          ，   rights  
        for (int i = n - 1; i >= 1; i--)
        {
            t = i;
            while (t < n && a[i] <= a[t + 1])   t = rights[t + 1];      //      t + 1      
            rights[i] = t;
        }
        max_area = -9999;
        for (int i = 1; i <= n; i++)
        {
            max_area = max((rights[i] - lefts[i] + 1) * a[i] , max_area);
        }
        cout << max_area << endl;
    }
    return 0;
}