题目

题目描述：
柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形。
但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数。
分别为a[i]a[i],每个矩形的高度是h[i]h[i],现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。

输入描述：
一行一个整数N，表示长方形的个数
接下来一行N个整数表示每个长方形的宽度
接下来一行N个整数表示每个长方形的高度

输出描述：
一行一个整数，表示最大的矩形面积

解析

1）知识点

  • 这道题是一道考察单调栈的题目，也就是栈的一种应用。

2）看题目

  • 首先题目很清楚，要我们在这张图里面找出面积最大的矩形。

3）算法分析

  1. 我们以前也写过类似的题目，用的是dp。思想差不多，但这道题用的是栈。不过都是从左到右进行遍历。
  2. 首先是什么叫单调栈呢：
    1. 很简单，就是栈里面的数据是单调的（比如单调递增或是单调递减啊）。
  3. 那这道题我们为什么会想到单调栈呢。
    1. 首先我们假设栈元素单调，且为单调递增。
    2. 因为如果后面的矩形高度比上一个矩形的高度高，说明这两个矩形用来计算的高度（在包括当前计算的第一个矩形的情况下），
      一定是以第一个的高度来计算的。（如图）
  4. 所以可以当我们碰到比上一个矮的（也就是打破了单调栈规则的）数据时，我们就可以把前面的数据进行计算，并使其变回单调栈。
    例图如上，我们可以删掉比新进的高的两个矩（因为前面比他高的一定可以算进去，就没用了），
    这时候只要把宽度给新的矩阵就行了（表述高出去的部分失去了意义）。

4）算法操作

  1. 这里我们要注意遍历的过程。
  2. 首先如果后面的数据比前面的要大，就自然的加入： 
    if (h[i] >= st_h[top]) {
    top++; 
    st_h[top] = h[i]; 
    st_w[top] = w[i];
}
  3. 但如果后面的数据比上一个要小，就要删除数据，合并矩阵了： 
    else {
    ll width = 0;
    while (h[i] <= st_h[top]) {
            width += st_w[top];
         ans = max(ans, width * st_h[top]);
        top--;
    }
    top++;
    st_h[top] = h[i];
    st_w[top] = width + w[i];
}
  4. 这里要特别注意，我们的循环要进行n+1次： 
    for (int i = 1; i <= n + 1; i++)
//为什么呢，因为我们要保证栈底元素也要进行判断，也就是最低的一层
//题目这里数据给锅了，所以更要注意这一点
  5. 除此之外呢，因为这里不是多组数据，但是还是要注意到一点，也就是设置第n+1个数据： 
    h[n  +  1]  =  0;

5）打代码

  1. 首先当然是输入数据。
  2. 然后我们手动模拟一个栈。
  3. 接下来就按照上面进行栈操作，轮流计算。
  4. 看我代码趴~

AC代码 

#include <iostream>
#include  <algorithm>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//预处理

const int MAX = 1e6 + 7;
int w[MAX], h[MAX];
ll st_h[MAX], st_w[MAX], top;
//全局变量

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) cin >> h[i];
    //输入

    h[n  +  1]  =  w[n  +  1]  = top = 0;
    ll ans = 0;
    for (int i = 1; i <= n + 1; i++) {
        if (h[i] >= st_h[top]) {
            top++; 
            st_h[top] = h[i]; 
            st_w[top] = w[i];
        }
        else {
            ll width = 0;
            while (top  &&  h[i] <= st_h[top]) {
                width += st_w[top];
                ans = max(ans, width * st_h[top]);
                top--;
            }
            top++;
            st_h[top] = h[i];
            st_w[top] = width + w[i];
        }
    }
    //操作

    cout << ans << endl;
    //输出

    return 0;
}
//函数体