农田最大产出评估

题意

有 $n$ 个连续地块，每个地块有一个肥力指数。选取任意一段连续的地块，这段地块的"产出系数"等于段内最小肥力指数乘以地块数量。求所有连续子段中最大的产出系数。

思路

先想想暴力怎么做：枚举所有区间 $[l, r]$ ，找区间最小值再乘以长度。这是 $O(n^2)$ 的， $n$ 到 $10^5$ 会超时。

换个角度想——如果我们固定"谁是区间里的最小值"呢？

假设第 $i$ 个地块的肥力 $a[i]$ 是某个区间的最小值，那这个区间最远能往左延伸到哪里？往右延伸到哪里？答案就是：往左找到第一个比 $a[i]$ 小的位置 $L$ ，往右找到第一个比 $a[i]$ 小的位置 $R$ ，那以 $a[i]$ 为最小值的最宽区间就是 $(L, R)$ ，宽度为 $R - L - 1$ ，产出系数就是 $a[i] \times (R - L - 1)$ 。

怎么高效求每个位置左边和右边第一个更小的元素？这正是单调栈的经典用法。

维护一个栈底到栈顶递增的单调栈：

从左往右扫一遍，求出每个位置左边第一个严格小于它的位置 $\text{left}[i]$ 。
从右往左扫一遍，求出每个位置右边第一个严格小于它的位置 $\text{right}[i]$ 。

最后遍历每个位置，取 $a[i] \times (\text{right}[i] - \text{left}[i] - 1)$ 的最大值即可。

复杂度

时间复杂度： $O(n)$ ，每个元素最多入栈出栈各一次。
空间复杂度： $O(n)$ 。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    vector<int> left(n), right(n);
    stack<int> st;
    for(int i=0;i<n;i++){
        while(!st.empty() && a[st.top()]>=a[i]) st.pop();
        left[i] = st.empty()? -1 : st.top();
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i=n-1;i>=0;i--){
        while(!st.empty() && a[st.top()]>=a[i]) st.pop();
        right[i] = st.empty()? n : st.top();
        st.push(i);
    }
    long long ans=0;
    for(int i=0;i<n;i++){
        long long w = right[i]-left[i]-1;
        ans = max(ans, (long long)a[i]*w);
    }
    printf("%lld\n",ans);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(br.readLine().trim());
        }
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && a[st.peek()] >= a[i]) st.pop();
            left[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && a[st.peek()] >= a[i]) st.pop();
            right[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            long w = right[i] - left[i] - 1;
            ans = Math.max(ans, (long) a[i] * w);
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    left = [0] * n
    right = [0] * n
    st = []
    for i in range(n):
        while st and a[st[-1]] >= a[i]:
            st.pop()
        left[i] = st[-1] if st else -1
        st.append(i)
    st.clear()
    for i in range(n - 1, -1, -1):
        while st and a[st[-1]] >= a[i]:
            st.pop()
        right[i] = st[-1] if st else n
        st.append(i)
    ans = 0
    for i in range(n):
        w = right[i] - left[i] - 1
        ans = max(ans, a[i] * w)
    print(ans)

solve()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = [];
    for (let i = 1; i <= n; i++) a.push(parseInt(lines[i]));
    const left = new Array(n);
    const right = new Array(n);
    const st = [];
    for (let i = 0; i < n; i++) {
        while (st.length > 0 && a[st[st.length - 1]] >= a[i]) st.pop();
        left[i] = st.length === 0 ? -1 : st[st.length - 1];
        st.push(i);
    }
    st.length = 0;
    for (let i = n - 1; i >= 0; i--) {
        while (st.length > 0 && a[st[st.length - 1]] >= a[i]) st.pop();
        right[i] = st.length === 0 ? n : st[st.length - 1];
        st.push(i);
    }
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const w = right[i] - left[i] - 1;
        ans = Math.max(ans, a[i] * w);
    }
    console.log(ans);
});