题目大意

用最少的矩形个数来覆盖图形

思路

这里介绍一种单调栈的做法：我们把他们看成一个个柱子，每一个柱子都可以用一个矩形来覆盖当我们拿到一个新的柱子时，如果他和前一个柱子一样高，那我们只需要把矩形拉宽一格就可以了如果他比前一个高，那么把矩形拉宽一格后再加一个矩形放在上面如果比前一个低，那就在一个单调栈里找到之前第一个小于等于他高度的柱子。等于就覆盖，小于就新加一个矩形。

代码如下

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 10;
int n, a[N], ans = 0;
stack<int> s;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; ++i) {
        if (s.empty()) {
            s.push(a[i]);
            ans++;
        } else if (a[i] > s.top()) {
            ans++;
            s.push(a[i]);
        } else {
            while (!s.empty() && a[i] < s.top()) s.pop();
            if (s.empty() || s.top() < a[i]) {
                s.push(a[i]);
                ans++;
            }
        }
    }

    cout << ans;

    return 0;
}