[BZOJ1595] [Usaco2008 Jan]人工湖（单调栈）

好的，这是一道经典的单调栈问题。题目描述如下：

有 $n$ 个湖，第 $i$ 个湖有一个高度 $h_i$。现在要在这些湖之间挖一些沟渠，使得相邻的湖之间的高度差不超过 $d$。请问最少需要挖多少个沟渠。

这是一道单调栈的典型应用题。我们可以从左到右遍历湖的高度，同时使用一个单调栈来维护之前所有湖的高度。具体来说，我们维护一个单调递增的栈，栈中存储的是湖的下标。假设当前遍历到第 $i$ 个湖，我们需要在之前的湖中找到一个高度最接近 $h_i$ 且高度不超过 $h_i-d$ 的湖，然后从这个湖到第 $i$ 个湖之间挖一条沟渠。具体的实现可以参考下面的代码：

#include <cstdio>
#include <stack>
using namespace std;

const int N = 100010;

int n, d;
int h[N];
stack<int> stk;

int main()
{
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n; i++)
        scanf("%d", &h[i]);

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        while (!stk.empty() && h[stk.top()] <= h[i] - d)
            stk.pop();
        if (!stk.empty())
            ans++;
        stk.push(i);
    }

    printf("%d\n", ans);
    return 0;
}

这里的关键在于，当我们遍历到第 $i$ 个湖时，所有比 $h_i-d$ 小的湖都可以被舍弃，因为它们不可能成为第 $i$ 个湖的前驱。因此，我们可以不断地从栈顶弹出比 $h_i-d$ 小的湖，直到栈顶的湖高度大于 $h_i-d$，然后将 $i$ 入栈。这样，栈中存储的就是当前 $h_i$ 左边所有高度不超过 $h_i-d$ 的湖，栈顶元素就是最靠近 $h_i$ 且高度不超过 $h_i-d$ 的湖。如果栈不为空，说明找到了一个前驱湖，答案加一。