一、题意

每组数据中输入一个宽度为n的平面直方图。
要求你输出直方图中面积最大的矩形的面积。

二、解析

超经典的直方图中求最大矩形问题。
从0开始从左向右遍历直方图，并维护一个单调栈。单调栈里存放到当前位置为止的一个单调递增的直方图高度，栈里实际存放的是下标。这样就可以在O(1)时间获取离当前位置最近的一个比当前值小的值的下标位置。通过下标只差可以算出当前左侧最大矩形的宽度，高度则就是栈顶元素值。这样就可以求出当前矩形的面积，然后维护面积的最大值到ans即可。

单调栈的维护方法：

  1. 先用while语句弹出栈顶中比当前遍历到的值还大的元素。
  2. 将当前遍历到的值压入栈中。

三、代码

#include <iostream>
#include <stack>
// #include <cmath>
#define max(x, y) ((x)>(y)?(x):(y))
using namespace std;
using LL = long long;
const int maxn = 100000 + 5;
int n;
int a[maxn];

int main() {
    while(cin >> n && n) {
        for(int i = 0; i < n; i ++) cin >> a[i];
        a[n] = 0;
        LL ans = 0;
        stack<int> stk;
        for(int i = 0; i <= n; i ++) {
            while(!stk.empty() && a[stk.top()] > a[i]) {
                int temp = stk.top();
                stk.pop();
                int height = a[temp];
                int width = (stk.empty() ? i : i - stk.top() - 1);  // 注意这里矩形的左边界是栈中前一个元素idx加1
                ans = max(ans, (LL)height * width);
            }
            stk.push(i);
        }
        cout << ans << endl;
    }
}

四、归纳

  • 单调栈模板（以单调递增栈为例）：
          stack<int> stk;
      for(int i = 0; i <= n; i ++) {
          while(!stk.empty() && a[stk.top()] > a[i]) {  // 先将大于当前值的元素弹出
              int temp = stk.top();
              stk.pop();
              ......  // Do something else
          }
          ......  // Do something else
          stk.push(i);  // 把当前值压栈
      }
  • 单调递增栈作用：获取离当前位置最近的一个小于当前值的元素。
  • 单调递减栈作用：获取离当前位置最近的一个大于当前值的元素。