最大矩形面积

单调栈结构的典型应用，代码如下：

//
// Created by jt on 2020/9/2.
//
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

int monotoneStack(vector<int> &vec);

int main() {
    int n;
    cin >> n;
    vector<int> vec;
    for (int i = 0; i < n; ++i) { int a; cin >> a; vec.push_back(a); }
    cout << monotoneStack(vec) << endl;
}


int monotoneStack(vector<int> &vec) {
    vec.push_back(0);
    int maxVal = 0;
    stack<int> st;
    for (int i = 0; i < vec.size(); ++i) {
        while(!st.empty() && vec[i] < vec[st.top()]) {
            int height = vec[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - (left+1);
            maxVal = max(maxVal, height * width);
        }
        st.push(i);
    }
    return maxVal;
}