接雨水问题
**接雨水问题**
**题目描述**
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:可以接 6 个单位的雨水(蓝色部分表示雨水)。
**解题思路**
这个问题可以通过多种方法解决,我们从最直观的暴力法开始,逐步优化到最优解。
**方法一:暴力法(按列计算)**
核心思想:对于每个柱子,找出其左边和右边的最高柱子,然后计算该柱子能接的雨水
2025-11-07 21:22:24
0