牛客549H 小A的柱状图

zz单调栈题。

刚学会单调栈zbl。

#include <iostream>
#include <utility>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1e6 + 10;
int_t height[LARGE + 1];
int_t width[LARGE + 1];
int_t left[LARGE + 1], right[LARGE + 1];
std::vector<int_t> stack;
int n;
int main() {
    scanf("%d", &n);
    for (int_t i = 1; i <= n; i++) {
        // int_t x;
        scanf("%lld", &width[i]);
        width[i] += width[i - 1];
    }
    for (int_t i = 1; i <= n; i++) {
        scanf("%lld", &height[i]);
    }
    stack.push_back(0);
    for (int_t i = 1; i <= n; i++) {
        while (height[stack.back()] >= height[i]) stack.pop_back();
        left[i] = stack.back() + 1;
        stack.push_back(i);
        // cout << "letf " << i << " = " << left[i] << endl;
    }
    stack.clear();
    stack.push_back(n + 1);
    for (int_t i = n; i >= 1; i--) {
        while (height[stack.back()] >= height[i]) stack.pop_back();
        right[i] = stack.back() - 1;
        stack.push_back(i);
    }
    int_t result = 0;
    for (int_t i = 1; i <= n; i++)
        result = std::max(result,
                          height[i] * (width[right[i]] - width[left[i] - 1]));
    cout << result << endl;
    return 0;
}