题解 | #农田最大产出评估#

题目链接

题目描述

给定一个代表 $N$ 个连续地块肥力指数的正整数数组。对于任意一个连续的地块组合（子数组），其“产出系数”定义为：

产出系数 = 组内最低肥力指数 * 组内地块数量

你需要计算所有可能的连续地块组合的产出系数，并返回其中的最大值。

解题思路

这是一个求解“最大矩形面积”问题的经典变种。如果直接枚举所有连续子数组（共 $\mathcal{O}(N^2)$ 个）并计算它们的产出系数，总时间复杂度会达到 $\mathcal{O}(N^2)$ 或 $\mathcal{O}(N^3)$ ，对于 $N$ 较大的情况会超时。

更高效的思路是转变视角：我们不枚举子数组，而是枚举每个地块 i，并假设它的肥力指数 fertility[i] 是某个最优子数组中的最小值。

基于这个假设，为了让 fertility[i] * 长度 这个乘积最大化，我们需要找到以 i 为中心、且 fertility[i] 确实是最小值的最长连续子数组。

这个最长的子数组由两个边界决定：

左边界: 从 i 向左走的第一个肥力指数小于 fertility[i] 的地块。
右边界: 从 i 向右走的第一个肥力指数小于 fertility[i] 的地块。

如果能为每个地块 i 快速找到这两个边界，问题就解决了。这正是单调栈 (Monotonic Stack) 擅长解决的问题。

算法步骤:

寻找所有元素的右侧更小值:
- 使用一个单调递增栈，从右向左遍历肥力数组。
- 对于当前元素 fertility[i]，不断弹出栈顶元素，直到栈顶元素的肥力小于 fertility[i]。
- 此时的栈顶就是 i 右侧第一个更小的元素。如果栈为空，说明右侧没有更小的元素。
- 将结果存入 right 数组，right[i] 表示 i 右侧第一个更小元素的索引。
寻找所有元素的左侧更小值:
- 同样使用一个单调递增栈，这次从左向右遍历。
- 用类似的方法，找到每个元素 i 左侧第一个更小的元素，并将结果存入 left 数组。
计算最大产出:
- 在得到 left 和 right 两个边界数组后，遍历每个地块 i。
- 对于地块 i，它作为最小值的最大区间宽度是 right[i] - left[i] - 1。
- 计算 fertility[i] * (right[i] - left[i] - 1)，并用它来更新全局的最大产出系数。

整个算法通过三次线性遍历完成，总时间复杂度为 $\mathcal{O}(N)$ 。

代码

cpp
java
python

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

using namespace std;

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

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

    vector<int> left(n), right(n);
    stack<int> s;

    // 寻找每个元素左边第一个更小的元素
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && fertility[s.top()] >= fertility[i]) {
            s.pop();
        }
        left[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }

    while (!s.empty()) s.pop();

    // 寻找每个元素右边第一个更小的元素
    for (int i = n - 1; i >= 0; --i) {
        while (!s.empty() && fertility[s.top()] >= fertility[i]) {
            s.pop();
        }
        right[i] = s.empty() ? n : s.top();
        s.push(i);
    }

    long long max_output = 0;
    for (int i = 0; i < n; ++i) {
        long long width = right[i] - left[i] - 1;
        max_output = max(max_output, fertility[i] * width);
    }

    cout << max_output << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Stack;
import java.util.Arrays;

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

        int[] left = new int[n];
        int[] right = new int[n];
        Stack<Integer> stack = new Stack<>();

        // 寻找每个元素左边第一个更小的元素
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && fertility[stack.peek()] >= fertility[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        // 寻找每个元素右边第一个更小的元素
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && fertility[stack.peek()] >= fertility[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        long maxOutput = 0;
        for (int i = 0; i < n; i++) {
            long width = right[i] - left[i] - 1;
            maxOutput = Math.max(maxOutput, fertility[i] * width);
        }

        System.out.println(maxOutput);
    }
}

def main():
    n = int(input())
    fertility = []
    for _ in range(n):
        fertility.append(int(input()))

    left = [-1] * n
    right = [n] * n
    stack = []

    # 寻找每个元素左边第一个更小的元素
    for i in range(n):
        while stack and fertility[stack[-1]] >= fertility[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)

    stack = []

    # 寻找每个元素右边第一个更小的元素
    for i in range(n - 1, -1, -1):
        while stack and fertility[stack[-1]] >= fertility[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)

    max_output = 0
    for i in range(n):
        width = right[i] - left[i] - 1
        max_output = max(max_output, fertility[i] * width)
        
    print(max_output)

if __name__ == "__main__":
    main()

算法及复杂度

算法：单调栈
时间复杂度： $\mathcal{O}(N)$ ，其中 $N$ 是地块的总数。算法包含三次独立的线性遍历，每次遍历中，每个元素的索引最多入栈和出栈一次，因此总时间复杂度是线性的。
空间复杂度： $\mathcal{O}(N)$ ，用于存储单调栈（最坏情况下所有元素都入栈）以及左右边界数组。