题目描述与示例

题目描述

公元 2919 年，人类终于发现了一颗宜居星球——X 星。现想在 X 星一片连绵起伏的山脉间建一个天热蓄水库，如何选取水库边界，使蓄水量最大？

山脉用正整数数组 s 表示，每个元素代表山脉的高度。选取山脉上两个点作为蓄水库的边界，则边界内的区域可以蓄水，蓄水量需排除山脉占用的空间。蓄水量的高度为两边界的最小值。

如果出现多个满足条件的边界，应选取距离最近的一组边界。

输出边界下标（从 0 开始）和最大蓄水量；如果无法蓄水，则返回 0，此时不返回边界。

例如，当山脉为 s=[3,1,2]时，则选取 s[0]和 s[2]作为水库边界，最大蓄水量为 1，此时输出：0 2:1

当山脉 s = [3,2,1]时，不存在合理的边界，此时输出 0。

输入描述

一行正整数，用空格隔开，例如输入1 2 3表示 s = [1,2,3]

输出描述

当存在合理的水库边界时，输出左边界、空格、右边界、英文冒号、蓄水量，例如0 2:1 当不存在合理的水库边界时，输出 0。

说明

数组 s 满足：1 <= length(s) <= 10000，0 <= s[i] <= 10000

示例一

输入

1 9 6 2 5 4 9 3 7

输出

1 6:19

说明

经过分析，选取 s[1]和 s[6] 时，水库蓄水量为 3+7+4+5 = 19 为最大蓄水量

示例二

输入

1 8 6 2 5 4 8 3 7

输出

1 6:15

说明

经过分析，选取 s[1] 和 s[8] 时，水库蓄水量为 15；同样选取 s[1]和 s[6]时，水库蓄水量也为 15。由于后者下标距离小（为 5），故应选取后者。

示例三

输入

1 2 3

输出

0

说明

不存在合理的水库边界。

解题思路

注意，本题和LeetCode 42、接雨水 非常类似。区别在于，本题需要对每一个不同的凹槽进行单独计算，而不是计算总的蓄水量。

首先一定要先理解LeetCode 42、接雨水 的代码，本质上就是一个找凹槽的过程。

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        stack = list()
        for i, h in enumerate(height):
            # 反复弹出栈顶元素
            while stack and h >= height[stack[-1]]:
                # 凹槽底部
                top = height[stack.pop()]
                if stack:
                    # 凹槽高度：
                    # 【当前柱子】和【栈顶柱子】之间较小值，减去【低洼处高度】
                    d = min(height[stack[-1]], h) - top
                    # 凹槽宽度
                    # 【当前柱子】和【栈顶柱子】之间的下标差
                    w = i - stack[-1] - 1
                    # 更新答案
                    ans += d * w
            # 将【当前柱子】的下标加入栈顶
            stack.append(i)
        return ans

但在原题的基础上，本题的设问是要求找到蓄水最多的凹槽，而不是总蓄水量，因此我们需要想办法把单独统计每一个凹槽的蓄水量。

注意到，当出现一根柱子，其长度不小于左边任意柱子长度时，其左边的凹槽不会连通到右边，故其右边可能会形成一个新的凹槽。如下图的红色箭头和绿色箭头所指。

img

那么这就是找新凹槽的关键之处。对应到单调栈模拟的过程中，在while循环执行完毕之后，如果发现此时栈中不存在任何元素，即len(stack) == 0，这意味着当前遍历到的柱子h，不会短于其左边的任何一根柱子，此时其右边可能会形成新的凹槽，应该重置变量area = 0。

代码

Python

# 题目：2023Q1A-天然蓄水池
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：单调栈
# 相关题目：LeetCode42-接雨水
# 代码看不懂的地方，请直接在群上提问


# 输入高度数组
height = list(map(int, input().split()))
# 初始化单调栈
stack = list()
# 初始化蓄水池两个柱子的下标x，y
x, y = -1, -1
# 初始化全局最大蓄水量ans，每一个凹槽的面积area
ans = 0
area = 0

# 遍历和维护单调栈的过程
# 和LeetCode42-接雨水基本一致
# 区别在于需要考虑是否出现一个新的凹槽，来重置area
for i, h in enumerate(height):
    # 反复弹出栈顶元素，
    while stack and h >= height[stack[-1]]:
        # 凹槽底部
        top = height[stack.pop()]
        if stack:
            # 凹槽高度：
            # 【当前柱子】和【栈顶柱子】之间较小值，减去【低洼处高度】
            d = min(height[stack[-1]], h) - top
            # 凹槽宽度
            # 【当前柱子】和【栈顶柱子】之间的下标差
            w = i - stack[-1] - 1
            # 更新面积area
            area += d * w
            # 若此时area大于ans，更新答案
            if area > ans:
                ans = area
                x, y = stack[-1], i
            # 若此时area等于ans，则根据距离远近来更新x和y
            if area == ans:
                if y-x > i-stack[-1]:
                    x, y = stack[-1], i

    # 若退出弹出栈顶的循环后，栈中不存在任何元素
    # 说明此时没有比【当前柱子】更高的柱子
    # 后续形成的凹槽肯定是一个新的凹槽，因此重置area为0
    if len(stack) == 0:
        area = 0
    # 将【当前柱子】的下标加入栈顶
    stack.append(i)

# 根据ans的结果，输出答案
print(0) if ans == 0 else print("{} {}:{}".format(x, y, ans))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> height = new ArrayList<>();

        while (scanner.hasNextInt()) {
            height.add(scanner.nextInt());
        }

        int n = height.size();
        Stack<Integer> stack = new Stack<>();
        int x = -1, y = -1;
        int ans = 0, area = 0;

        for (int i = 0; i < n; i++) {
            int h = height.get(i);

            while (!stack.isEmpty() && h >= height.get(stack.peek())) {
                int top = height.get(stack.pop());

                if (!stack.isEmpty()) {
                    int d = Math.min(height.get(stack.peek()), h) - top;
                    int w = i - stack.peek() - 1;
                    area += d * w;

                    if (area > ans) {
                        ans = area;
                        x = stack.peek();
                        y = i;
                    }

                    if (area == ans && (y - x > i - stack.peek())) {
                        x = stack.peek();
                        y = i;
                    }
                }
            }

            if (stack.isEmpty()) {
                area = 0;
            }
            stack.push(i);
        }

        if (ans == 0) {
            System.out.println(0);
        } else {
            System.out.println(x + " " + y + ":" + ans);
        }
    }
}

C++

“`C++
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
vector<int> height;
int h;

<pre><code>while (cin >> h) {
height.push_back(h);
}

int n = height.size();
stack<int> st;
int x = -1, y = -1;
int ans = 0, area = 0;

for (int i = 0; i < n; i++) {
int h = height[i];

while (!st.empty() && h >= height[st.top()]) {
int top = height[st.top()];
st.pop();

if (!st.empty()) {
int d = min(height[st.top()], h) – top;
int w = i – st.top() – 1;
area += d * w;

if (area > ans) {
ans = area;
x = st.top();
y = i;
}

if (area == ans && (y – x > i – st.top())) {
x = st.top();
y = i;
}
}
}

if (st.empty()) {
area = 0;
}
st.push(i);
}

if (ans == 0) {
cout << 0 << endl;
} else {
cout << x << " " << y << ":" << ans << endl;
}

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(N)。元素入栈或出栈至多一次。

空间复杂度：O(N)。单调栈所占空间。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）

上一篇 【单调栈】2023C-回转寿司
下一篇 【队列】2023B-不开心的小朋友

相关文章