Planting Trees - 题解

标签与难度

标签: 动态规划, 二维问题降维, 单调队列, 滑动窗口, 枚举, 矩阵难度: 2000

题目大意喵~

各位爱思考的小伙伴们，大家好呀，喵~ ฅ'ω'ฅ

这道题是说，我们有一片 $N \times N$ 的山地，每个格子 $(i, j)$ 都有一个海拔高度 $a_{i,j}$ 。我们的任务是在这片山地上找一个矩形区域来种树。

但是有一个要求哦：在这个矩形区域里，所有格子的最高海拔和最低海拔之差不能超过一个给定的值 $M$ 。也就是说，对于选定的矩形区域， $\max(\text{海拔}) - \min(\text{海拔}) \le M$ 。

我们的目标是找到满足这个条件的、面积最大的矩形，然后告诉队长这个最大面积是多少，这样他才知道要准备多少树苗，的说！

输入:

多组测试数据。
每组数据第一行是两个整数 $N$ 和 $M$ ( $1 \le N \le 500$ , $0 \le M \le 10^9$ )。
接下来 $N$ 行，每行 $N$ 个整数，表示每个格子的海拔 $a_{i,j}$ 。

输出:

对每组数据，输出一个整数，表示满足条件的最大矩形面积。

解题思路分析

这道题想让我们在一个二维网格中找一个满足特定条件的、面积最大的子矩形。看到“最大子矩形”这类问题，咱的猫猫直觉就告诉咱，暴力枚举肯定是不行的呐！

如果我们暴力枚举所有可能的矩形，一个矩形由左上角 $(r_1, c_1)$ 和右下角 $(r_2, c_2)$ 决定，这就需要四层循环，复杂度是 $O(N^4)$ 。在循环内部，我们还要花 $O(N^2)$ 的时间去找到这个矩形内的最大值和最小值。总复杂度高达 $O(N^6)$ ，这对于 $N=500$ 来说，简直是天文数字，肯定会超时的说！

所以，我们必须想办法优化！这种二维问题，一个非常经典的思路就是降维打击！喵~ 我们能不能把它变成一个一维问题来解决呢？

答案是肯定的！我们可以尝试固定矩形的上下边界，然后去寻找最宽的左右边界。

核心思路：枚举上下边界，降维成一维问题

我们先枚举矩形的上边界 top_row，从第 1 行到第 $N$ 行。
然后，我们再枚举矩形的下边界 bottom_row，从 top_row 行到第 $N$ 行。

当我们固定了 top_row 和 bottom_row 后，我们就锁定了一个高度为 bottom_row - top_row + 1 的横向条带。现在问题就变成了：在这个条带内，找到一个最宽的子矩形，使其满足海拔差不超过 $M$ 的条件。

为了解决这个“新”问题，我们先预处理一下这个条带的信息。对于条带中的每一列 c，我们计算出它在 top_row 到 bottom_row 之间的最大海拔和最小海拔。

col_max[c] = max(a[i][c]) for i from top_row to bottom_row.
col_min[c] = min(a[i][c]) for i from top_row to bottom_row.

这样，我们就得到了两个一维数组 col_max 和 col_min。现在，我们最初的二维问题就被转化为了一个一维问题：

在一维数组 col_max 和 col_min 中，找到一个最长的连续子数组区间 [left_col, right_col]，使得这个区间内 col_max 的最大值与 col_min 的最小值之差不超过 $M$ 。
$\max_{k=left\_col}^{right\_col} (\text{col\_max}[k]) - \min_{k=left\_col}^{right\_col} (\text{col\_min}[k]) \le M$

这个一维问题是不是看起来熟悉多了？这正是滑动窗口大显身手的好地方！

一维问题的滑动窗口解法

我们可以用一个右指针 right_ptr 不断向右扩展窗口，同时用一个左指针 left_ptr 在必要时向右收缩窗口。为了能在 $O(1)$ 的时间内查询到当前窗口内的最大值和最小值，我们需要一个神奇的工具——单调队列！

我们需要两个单调队列：

max_dq: 一个递减队列，用来维护当前窗口内 col_max 值的最大值。队首元素总是当前窗口最大值。
min_dq: 一个递增队列，用来维护当前窗口内 col_min 值的最小值。队首元素总是当前窗口最小值。

算法流程如下：

初始化左指针 left_ptr = 1。
用右指针 right_ptr 从 1 遍历到 $N$ ： a. 将当前 right_ptr 对应的值 col_max[right_ptr] 和 col_min[right_ptr] 加入两个单调队列。为了维持单调性，入队前要从队尾弹出不满足条件的元素。 b. 此时，max_dq 的队首就是窗口 [left_ptr, right_ptr] 内 col_max 的最大值，min_dq 的队首就是窗口内 col_min 的最小值。 c. 检查条件：max_dq.front() - min_dq.front() > M。如果条件不满足（差值过大），说明窗口需要收缩。我们不断地将 left_ptr 右移，并从两个队列的队首移除已经滑出窗口的元素，直到条件再次满足。 d. 当条件满足时，当前窗口 [left_ptr, right_ptr] 就是一个合法的区间。它的宽度是 right_ptr - left_ptr + 1。我们用这个宽度更新我们找到的最大宽度。

这个滑动窗口的过程是线性的，所以解决这个一维问题的时间复杂度是 $O(N)$ 。

整体算法与复杂度

好了，把所有部分组合起来，我们的最终算法就成型啦：

初始化最大面积 max_area = 0。
外层循环：for top_row from 1 to N
中层循环：for bottom_row from top_row to N a. 计算或更新 col_max 和 col_min 数组。当 bottom_row 从上一行移动到当前行时，我们不需要重新计算，只需用新一行 a[bottom_row] 的值来更新 col_max 和 col_min 即可。这一步耗时 $O(N)$ 。 b. 调用滑动窗口算法，在 $O(N)$ 时间内找到最大合法宽度 max_width。 c. 计算当前候选矩形的面积：area = (bottom_row - top_row + 1) * max_width。 d. 更新 max_area = max(max_area, area)。

总的时间复杂度是 $O(N \times N \times (N+N)) = O(N^3)$ 。对于 $N=500$ ， $N^3 \approx 1.25 \times 10^8$ ，这是完全可以接受的！空间复杂度主要是存储 col_max 和 col_min 数组，以及单调队列，为 $O(N)$ 。

这思路就像我的猫爪一样，一步一步，稳稳地抓住问题的核心，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，变量名和注释都力求清晰，希望能帮助你理解呐！

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

const int INF = 2e9; // 一个足够大的数作为初始最小值

// 使用滑动窗口和单调队列解决一维问题
// 返回在 col_max 和 col_min 数组上满足条件的最长子数组宽度
int find_max_width(int n, int m, const vector<int>& col_max, const vector<int>& col_min) {
    int max_w = 0;
    // max_dq 存储 col_max 的递减序列的索引
    // min_dq 存储 col_min 的递增序列的索引
    deque<int> max_dq, min_dq;
    int left_ptr = 0; // 滑动窗口的左边界 (0-indexed)

    for (int right_ptr = 0; right_ptr < n; ++right_ptr) {
        // 维护 max_dq 的单调递减性
        while (!max_dq.empty() && col_max[max_dq.back()] <= col_max[right_ptr]) {
            max_dq.pop_back();
        }
        max_dq.push_back(right_ptr);

        // 维护 min_dq 的单调递增性
        while (!min_dq.empty() && col_min[min_dq.back()] >= col_min[right_ptr]) {
            min_dq.pop_back();
        }
        min_dq.push_back(right_ptr);

        // 当窗口内的极差大于 M 时，收缩窗口左边界
        while (!max_dq.empty() && !min_dq.empty() && 
               col_max[max_dq.front()] - col_min[min_dq.front()] > m) {
            // 如果队首元素即将滑出窗口，则将其弹出
            if (max_dq.front() == left_ptr) {
                max_dq.pop_front();
            }
            if (min_dq.front() == left_ptr) {
                min_dq.pop_front();
            }
            left_ptr++; // 移动左指针
        }
        
        // 更新最大宽度
        max_w = max(max_w, right_ptr - left_ptr + 1);
    }
    return max_w;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }

    long long max_area = 0;

    // 枚举矩形的上边界
    for (int top_row = 0; top_row < n; ++top_row) {
        // col_max[j] 存储从 top_row 到当前 bottom_row 在第 j 列的最大值
        // col_min[j] 存储从 top_row 到当前 bottom_row 在第 j 列的最小值
        vector<int> col_max(n, 0);
        vector<int> col_min(n, INF);

        // 枚举矩形的下边界
        for (int bottom_row = top_row; bottom_row < n; ++bottom_row) {
            // 更新 col_max 和 col_min 数组以包含新的一行 (bottom_row)
            for (int j = 0; j < n; ++j) {
                col_max[j] = max(col_max[j], a[bottom_row][j]);
                col_min[j] = min(col_min[j], a[bottom_row][j]);
            }

            // 降维成一维问题，用滑动窗口求解
            int width = find_max_width(n, m, col_max, col_min);
            int height = bottom_row - top_row + 1;
            
            if (width > 0) { // 只有找到有效宽度时才更新面积
                max_area = max(max_area, (long long)height * width);
            }
        }
    }
    cout << max_area << endl;
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N^3)$ 我们有三层嵌套的循环。最外两层循环用于枚举矩形的上下边界 top_row 和 bottom_row，这部分的组合有 $O(N^2)$ 种。在最内层，我们首先花 $O(N)$ 的时间更新 col_max 和 col_min 两个一维数组，然后调用 find_max_width 函数。这个函数使用滑动窗口和单调队列，其内部的每个元素最多入队一次、出队一次，所以它的复杂度是 $O(N)$ 。因此，总的时间复杂度为 $O(N^2 \times (N + N)) = O(N^3)$ 。
空间复杂度: $O(N)$ 我们需要一个二维数组 a 来存储输入的海拔数据，大小为 $O(N^2)$ 。然而，在 solve 函数的循环体内部，我们使用了 col_max、col_min 两个辅助数组，以及两个单调队列 max_dq 和 min_dq。它们的大小都与 $N$ 线性相关，所以主要的额外空间开销是 $O(N)$ 。如果输入数据可以边读边处理，理论上可以优化到 $O(N)$ ，但通常我们认为输入数据占用的空间不计入额外空间复杂度，所以说 $O(N)$ 是很合理的分析。

知识点总结

这道题真是一道非常好的练习题，融合了好几个重要的知识点呢！

降维思想: 解决高维（这里是二维）问题时，通过固定一个或多个维度，将其转化为更低维度的、更容易解决的问题。这是算法设计中非常强大和常用的技巧。
滑动窗口: 对于求解数组/字符串中满足特定条件的“最长”或“最短”连续子区间问题，滑动窗口是一个高效的算法框架。它通过维护一个可变大小的窗口，避免了大量的重复计算。
单调队列: 单调队列是滑动窗口的“黄金搭档”，喵~ 它可以高效地（均摊 $O(1)$ ）获取并维护一个滑动窗口内的最大值或最小值。其核心是维持队列内元素的单调性，从而保证队首永远是当前窗口的最值。
枚举与优化: 从暴力枚举出发，思考如何优化计算过程，是提升解题能力的关键。本题就是从 $O(N^6)$ 的暴力枚举，通过预处理和数据结构优化，最终达到了 $O(N^3)$ 的可行解。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问我哦！一起加油，变得更强吧，喵~ ＞ω＜

Planting Trees - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​