Solutions CS101

Appearance

26977: 接雨水 ​

stack, dp, math, http://cs101.openjudge.cn/practice/26977/

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

img

height = [0,1,0,2,1,0,1,3,2,1,2,1]

由数组表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

输入

第一行包含一个整数n。1 <= n <= 2 * 10^4 第二行包含n个整数，相邻整数间以空格隔开。0 <= ratings[i] <= 2 * 10^5

输出

一个整数

样例输入

sample1 input:
12
0 1 0 2 1 0 1 3 2 1 2 1

sample1 output:
6

样例输出

sample2 input:
6
4 2 0 3 2 5

sample2 output:
9

提示

tags: stack, dp, math

来源: 42.接雨水，https://leetcode.cn/problems/trapping-rain-water/

python
# DP
from typing import List

def trap(height: List[int]) -> int:
    if not height:
        return 0
    
    n = len(height)
    leftMax = [height[0]] + [0] * (n - 1)
    for i in range(1, n):
        leftMax[i] = max(leftMax[i - 1], height[i])

    rightMax = [0] * (n - 1) + [height[n - 1]]
    for i in range(n - 2, -1, -1):
        rightMax[i] = max(rightMax[i + 1], height[i])

    ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
    return ans

input()
*h, = map(int, input().split())
#h = [0,1,0,2,1,0,1,3,2,1,2,1]
ans = trap(h)
print(ans)
python
# 用于计算接雨水问题的函数，采用了单调栈的思想
def trap6(height):
    total_sum = 0
    stack = []
    current = 0
    while current < len(height):
        while stack and height[current] > height[stack[-1]]:
            h = height[stack[-1]]
            stack.pop()
            if not stack:
                break
            distance = current - stack[-1] - 1
            min_val = min(height[stack[-1]], height[current])
            total_sum += distance * (min_val - h)
        stack.append(current)
        current += 1
    return total_sum

input()
*h, = map(int, input().split())
#h = [0,1,0,2,1,0,1,3,2,1,2,1]
ans = trap6(h)
print(ans)