题解 | #灌注水箱#

题目链接

题目描述

有一个水箱，从左到右有 $n$ 个挡板，第 $i$ 个挡板的高度为 $h_i$ 。水从最左侧以每秒 1 个单位体积的速度注入。水在一个区域内的水位是均匀的。当一个区域的水位超过其右侧挡板的高度时，水会溢出到下一个区域。求每个挡板被溢过的最早时刻。

解题思路

直接模拟每一秒的水流过程显然会超时。这是一个动态规划问题，可以通过数据结构进行优化。

1. 核心模型：盆地填充

我们可以将注水过程看作是填充一系列“盆地”。每个挡板 $i$ 都是其左侧一个盆地的右边界。这个盆地的左边界，则是由左侧第一个高度大于或等于 $h_i$ 的挡板 $L_i$ 决定的。如果不存在这样的挡板，我们可以认为最左侧有一个无限高的 0 号挡板。

2. 建立递推关系

设 $V_i$ 为恰好将水蓄满到可以溢出第 $i$ 个挡板（即水位达到 $h_i$ ）时，所需要的总注水量。由于注水速度恒定，这个体积在数值上等于所需的时间。

要开始填充以 $i$ 为右边界的盆地 (L_i, i]，必须先完成对 $L_i$ 左侧所有盆地的填充，直到水可以溢出 $L_i$ 。这部分所需的水量为 $V_{L_i}$ 。
当水开始溢出 $L_i$ 后，它会流入 (L_i, i] 这个新的区域。这个区域的宽度为 $i - L_i$ 。
要让水溢出挡板 $i$ ，我们需要将这个宽度为 $i - L_i$ 的区域从底部填充到高度 $h_i$ 。这需要的新增水量为 $h_i \times (i - L_i)$ 。
因此，总注水量 $V_i$ 等于填充到 $L_i$ 的水量与填充新区域的水量之和。我们得到递推公式： $V_i = V_{L_i} + h_i \times (i - L_i)$
我们定义 $V_0 = 0$ 作为递推的起点。

3. 使用单调栈寻找 $L_i$

问题转化为如何为每个 $i$ 高效地找到 $L_i$ 。这是“寻找左侧第一个更高/相等元素”的经典问题，可以使用单调栈在 $\mathcal{O}(n)$ 的时间内解决。
我们维护一个存储挡板下标的栈，并保持栈中下标对应的挡板高度是单调递增的。

4. 最终答案

$V_i$ 是在第 $V_i$ 秒末，水位恰好达到 $h_i$ 所需的总水量/时间。
根据题目定义，水在下一个时间单位，即第 $V_i + 1$ 秒，才会“溢过”挡板。
因此，第 $i$ 个挡板的溢出时刻是 $V_i + 1$ 。

算法步骤：

使用单调栈，从左到右遍历挡板，在 $\mathcal{O}(n)$ 时间内计算出每个挡板 $i$ 对应的左边界 $L_i$ 。
根据递推公式 $V_i = V_{L_i} + h_i \times (i - L_i)$ ，在 $\mathcal{O}(n)$ 时间内计算出所有 $V_i$ 。
输出每个挡板的答案 $V_i + 1$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

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

    vector<int> left_taller(n + 1, 0);
    stack<int> s;

    for (int i = 1; i <= n; ++i) {
        while (!s.empty() && h[s.top()] <= h[i]) {
            s.pop();
        }
        if (!s.empty()) {
            left_taller[i] = s.top();
        }
        s.push(i);
    }

    vector<long long> v(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int l_idx = left_taller[i];
        v[i] = v[l_idx] + h[i] * (i - l_idx);
    }

    for (int i = 1; i <= n; ++i) {
        cout << v[i] + 1 << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] h = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            h[i] = sc.nextLong();
        }

        int[] leftTaller = new int[n + 1];
        Deque<Integer> s = new ArrayDeque<>();

        for (int i = 1; i <= n; i++) {
            while (!s.isEmpty() && h[s.peekLast()] <= h[i]) {
                s.pollLast();
            }
            if (!s.isEmpty()) {
                leftTaller[i] = s.peekLast();
            }
            s.offerLast(i);
        }

        long[] v = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            int lIdx = leftTaller[i];
            v[i] = v[lIdx] + h[i] * (i - lIdx);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(v[i] + 1).append(i == n ? "" : " ");
        }
        System.out.println(sb.toString());
    }
}

import sys

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)
    
    h_str = sys.stdin.readline()
    if not h_str: return
    h = [0] + list(map(int, h_str.split()))

    left_taller = [0] * (n + 1)
    s = []

    for i in range(1, n + 1):
        while s and h[s[-1]] <= h[i]:
            s.pop()
        if s:
            left_taller[i] = s[-1]
        s.append(i)

    v = [0] * (n + 1)
    for i in range(1, n + 1):
        l_idx = left_taller[i]
        v[i] = v[l_idx] + h[i] * (i - l_idx)

    ans = [val + 1 for val in v[1:]]
    print(*ans)

solve()

算法及复杂度

算法: 单调栈、动态规划
时间复杂度: 预处理 $L_i$ 和计算 $V_i$ 都只需要一次线性扫描，因此总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度: 需要额外的数组来存储 $L_i$ 和 $V_i$ ，以及一个单调栈，空间复杂度为 $\mathcal{O}(n)$ 。