AcWing 131. The largest rectangle in the histogram (monotone stack classic application template)

Pre knowledge ： Monotonic stack

The question ：

Given many column graphs , Each column The width is 1.

All the columns are close together .

We know Height of all columns h.

Find the area of the largest rectangle contained within the union of these columns （ In the following illustration , The answer is the area of the shadow ), Number of columns ≤ 10 ^ 5.

Ideas ：

Consider violence first , The height of each rectangle shall prevail , Extend to both sides , Until you meet someone shorter than it

As shown in the figure , Each rectangle i Extend to both sides , obviously When Extend left To The first rectangle position that is strictly smaller than the current height le[i] Stop when , The right same principle extends to ri[i]（ This is the classic use of monotone stack ）

The expanded rectangular area is s = (ri[i] - le[i] - 1) ∗ h[i]

The optimal solution will be generated in these extended rectangles .（ Violence O(n ^ 2)）

Monotone stack optimization

When calculating the left bound of each rectangle that can be extended , It can be found that some rectangles can be ignored

As shown in the figure , because 2 The existence of rectangle No , In the calculation 2 The left boundary of the rectangle on the right , Not to be considered 1 No. rectangle .

The height is higher than 2 The rectangle of number will be 2 Get stuck , The height is less than or equal to 2 No. must be less than or equal to 1 Number .

Observation can be seen , When calculating the left boundary , The left and higher rectangle can be omitted , So you can use Monotone stack optimization .

stk[tt] As Stack top element subscript , When Satisfy h[stk[tt]] >= h[i] when , eject To the top of the stack

Time complexity ：

$O(n)$

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e5 + 10;
int n;
int h[N];
int stk[N], tt;
int le[N], ri[N];

signed main()
{
    
    int T = 1; //cin >> T;

    while (T--)
    {
    
        while (cin >> n, n)
        {
    
            memset(le, 0, sizeof le);
            memset(ri, 0, sizeof ri);

            for (int i = 1; i <= n; ++i) scanf("%lld", &h[i]);

            tt = 0;
            for (int i = 1; i <= n; ++i)
            {
    
                while (tt && h[stk[tt]] >= h[i]) --tt;
                if (tt) le[i] = stk[tt];
                else le[i] = 0;
                stk[++tt] = i;
            }

            tt = 0;
            for (int i = n; i >= 1; --i)
            {
    
                while (tt && h[stk[tt]] >= h[i]) --tt;
                if (tt) ri[i] = stk[tt];
                else ri[i] = n + 1;
                stk[++tt] = i;
            }

            int res = -1;

            for (int i = 1; i <= n; ++i)
            {
    
                res = max(res, h[i] * (ri[i] - le[i] - 1));
            }

            cout << res << '\n';
        }

    }

    return 0;
}