【洛谷】P1318 积水面积

题目地址：

https://www.luogu.com.cn/problem/P1318

题目描述：
一组正整数，分别表示由正方体叠起的柱子的高度。若某高度值为$x$，表示由$x$个正立方的方块叠起（如下图，$0<=x<=5000$）。找出所有可能积水的地方（图中蓝色部分），统计它们可能积水的面积总和（计算的是图中的横截面积。一个立方体的位置，为一个单位面积）。如图：柱子高度变化为0 1 0 2 1 2 0 0 2 0

图中蓝色部分为积水面积，共有$6$个单位面积积水。

输入格式：
两行，第一行$n$，表示有$n$个数$(3<=n<=10000)$。第$2$行连续$n$个数表示依次由正方体迭起的高度，保证首尾为$0$。

输出格式：
一个数，可能积水的面积。

可以用单调栈。参考https://blog.csdn.net/qq_46105170/article/details/103840733。代码如下：

#include <iostream>
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;

const int N = 10010;
int n, top;
PII stk[N];

int main() {
    
  scanf("%d", &n);
  int res = 0;
  for (int i = 0; i < n; i++) {
    
    int c;
    scanf("%d", &c);
    while (top && stk[top - 1].y <= c) {
    
      int h = stk[--top].y;
      if (!top) break;
      res += (min(stk[top - 1].y, c) - h) * (i - stk[top - 1].x - 1);
    }
    stk[top++] = {
    i, c};
  }

  printf("%d\n", res);
}

时空复杂度$O(n)$。