jxcakak题解

经验分享区
1

jxcakak题解

题目描述

给定一个 w * h 的矩形，每个方格内有数，求一个 n \times n 的正方形，使得正方形内部最小值加最大值的值最小。你只需要输出这个数值。

思路

70pts做法

考试的时候实在想不出来怎么写，直接打暴力，4重循环枚举每一个可能的正方形中的最大值和最小值的和，最后找到最小的。

由于是非正解，所以本思路不附上核心代码。

100pts做法

首先，我们应该可以想到快速处理每一行中连续n个数的最大值：滑动窗口。

对于滑动窗口的做法，我们需要写一个双端队列deque。来维护其单调性。下面给出找到 n 个数之中最大值的做法。

  1. 将双端队列中加入 n 个元素，其中在最大值之前的数全部出队，形象的讲的话，假设最大值是大哥，在他之前的小弟永远无法当上大哥（因为滑动窗口滑动的时候他总是会先被舍去）
  2. 在新的元素入队的时候，检查当前队尾元素是否大于当前入队元素，如果不是，那么直接弹出。形象的讲的话：在当前大哥后面的小弟一定比大哥被舍去的时间晚，都有机会当上大哥，但是当新的队尾元素加入的时候，如果比当前队尾元素大的话，相当于他比你厉害还会比你后舍去，那么你就永远无法当上大哥，直接删除即可。
  3. 每次滑动之后，需要将队首元素弹出，当然如果当前元素已经被弹出（在1中被弹出）则不需要弹出。形象的讲，像是自然死亡。

当然，最小值的处理方法类似。

但是还有一个问题：滑动窗口是在一维数组中实现的，现在是一个二维数组怎么办？

当然，我们有时候会想到：那我们竖着再处理一次不就好了，但是这样会导致时间复杂度直接炸掉TLE。我们可以利用现成的数据：横着处理过的最大值和最小值。然后直接使用这个数据处理竖着的最大值和最小值。

这样我们就得到了所有的最大值和最小值。

最后我们一个双重循环找出最大值和最小值就可以了。

附上代码（滑动窗口部分）：

    for (int x = 1; x <= w; ++x) {
        deque<int> dq_max, dq_min;
        for (int j = 1; j <= h; ++j) {
            while (!dq_max.empty() && a[x][j] >= a[x][dq_max.back()])
                dq_max.pop_back();
            dq_max.push_back(j);
            while (dq_max.front() <= j - n)
                dq_max.pop_front();

            while (!dq_min.empty() && a[x][j] <= a[x][dq_min.back()])
                dq_min.pop_back();
            dq_min.push_back(j);
            while (dq_min.front() <= j - n)
                dq_min.pop_front();

            if (j >= n) {
                row_max[x][j - n + 1] = a[x][dq_max.front()];
                row_min[x][j - n + 1] = a[x][dq_min.front()];
            }
        }
    }

    int cols = h - n + 1;
    int rows = w - n + 1;
    for (int y = 1; y <= cols; ++y) {
        deque<int> dq_max, dq_min;
        for (int x = 1; x <= w; ++x) {

            while (!dq_max.empty() && row_max[x][y] >= row_max[dq_max.back()][y])
                dq_max.pop_back();
            dq_max.push_back(x);
            while (dq_max.front() <= x - n)
                dq_max.pop_front();

            while (!dq_min.empty() && row_min[x][y] <= row_min[dq_min.back()][y])
                dq_min.pop_back();
            dq_min.push_back(x);
            while (dq_min.front() <= x - n)
                dq_min.pop_front();

            if (x >= n) {
                max_val[x - n + 1][y] = row_max[dq_max.front()][y];
                min_val[x - n + 1][y] = row_min[dq_min.front()][y];
            }
        }
    }
2 个赞