网站开发内容,wordpress 公式编辑器,网站建设太金手指六六六,网易企业邮箱电话链接#xff1a;https://leetcode.cn/problems/trapping-rain-water 题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 思路分析 首先#xff0c;我们需要遍历数组#xff0c;对于每个元素https://leetcode.cn/problems/trapping-rain-water 题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 思路分析 首先我们需要遍历数组对于每个元素我们将其高度与栈顶元素的高度进行比较。如果当前元素的高度小于栈顶元素的高度我们将当前元素的索引入栈如果当前元素的高度大于或等于栈顶元素的高度我们将栈顶元素出栈并计算出栈元素对应的雨水量。 AC代码
class Solution {
public:int trap(vectorint height) {int n height.size();int ans 0;stackint stk;for (int i 0; i n; i) {while (!stk.empty() height[i] height[stk.top()]) {int top stk.top();stk.pop();if (stk.empty()) break;int distance i - stk.top() - 1;int bounded_height min(height[i], height[stk.top()]) - height[top];ans distance * bounded_height;}stk.push(i);}return ans;}
};代码解释 这段代码中我们首先定义了一个栈 stk用于存储数组中元素的索引。然后我们遍历数组对于每个元素我们将其高度与栈顶元素的高度进行比较。如果当前元素的高度小于栈顶元素的高度我们将当前元素的索引入栈如果当前元素的高度大于或等于栈顶元素的高度我们将栈顶元素出栈并计算出栈元素对应的雨水量。最后我们返回所有计算出的雨水量之和即可。
需要注意的是在计算雨水量时我们需要考虑当前元素与栈顶元素之间的距离以及当前元素和栈顶元素之间的最小高度。这是因为雨水量是由当前元素和栈顶元素之间的距离和最小高度共同决定的。
