【每日一题】小A的柱状图

Description

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

Solution

单调栈的经典题目，但是我因为太久没做题，忘了一些细节的处理，都在代码里面标注上了。简单的说就是维护一个单调递增的序列，当遇到递减的情况时，检验前面所有可形成矩形的方案，更新答案。

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 5;
const int mod = 9973;

ll l[N], r[N];

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n; cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> l[i];
    l[i] += l[i - 1];
  }
  for(int i = 1; i <= n; i++) {
    cin >> r[i];
  }
  stack<int> st;
  long long ans = 0;
  r[n + 1] = 0; // 防止剩下矩形没有弹出栈
  st.push(0); // 防止里面越界
  for(int i = 1; i <= n + 1; i++) {
    if(st.empty() || r[i] >= r[st.top()]) st.push(i);
    else {
      while(!st.empty() && r[st.top()] > r[i]) {
        int k = st.top();
        st.pop(); // 如果没push 0, 下面一句会越界
        ans = max(ans, (l[i - 1] - l[st.top()]) * r[k]);
      }
      st.push(i);
    }
  }
  cout << ans << "\n";
  return 0;
}