恒一信息深圳网站建设公司2,开发一个app需要什么技能,北京响应式网站设计,山东住房和城乡建设厅网站一体化平台【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主#xff0c;题解使用C语言。#xff08;若有使用其他语言的同学也可了解题解思路#xff0c;本质上语法内容一致题解使用C语言。若有使用其他语言的同学也可了解题解思路本质上语法内容一致 【题目描述】
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
【示例一】 输入height [0,1,0,2,1,0,1,3,2,1,2,1]
输出6
解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。
【示例二】
输入height [4,2,0,3,2,5]
输出9
【提示及数据范围】
n height.length1 n 2 * 10的4次方0 height[i] 10的5次方
【代码】
// 方法一动态规划// 对于下标 i下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值
// 下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。
// 创建两个长度为 n 的数组 leftMax 和 rightMax。
// 对于 0≤inleftMax[i] 表示下标 i 及其左边的位置中height 的最大高度
// rightMax[i] 表示下标 i 及其右边的位置中height 的最大高度。// leftMax[0]height[0]rightMax[n−1]height[n−1]。两个数组的其余元素的计算如下// 当 1≤i≤n−1 时leftMax[i]max(leftMax[i−1],height[i])// 当 0≤i≤n−2 时rightMax[i]max(rightMax[i1],height[i])。// 因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值
// 反向遍历数组 height 得到数组 rightMax 的每个元素值。// 在得到数组 leftMax 和 rightMax 的每个元素值之后
// 对于 0≤in下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。
// 遍历每个下标位置即可得到能接的雨水总量。class Solution {
public:int trap(vectorint height) {int n height.size();if (n 0) {return 0;}vectorint leftMax(n);leftMax[0] height[0];for (int i 1; i n; i) {leftMax[i] max(leftMax[i - 1], height[i]);}vectorint rightMax(n);rightMax[n - 1] height[n - 1];for (int i n - 2; i 0; --i) {rightMax[i] max(rightMax[i 1], height[i]);}int ans 0;for (int i 0; i n; i) {ans min(leftMax[i], rightMax[i]) - height[i];}return ans;}
};//方法二单调栈// 维护一个单调栈单调栈存储的是下标满足从栈底到栈顶的下标对应的数组 height 中的元素递减。// 从左到右遍历数组遍历到下标 i 时如果栈内至少有两个元素记栈顶元素为 top
// top 的下面一个元素是 left则一定有 height[left]≥height[top]。// 如果 height[i]height[top]则得到一个可以接雨水的区域该区域的宽度是 i−left−1
// 高度是 min(height[left],height[i])−height[top]
// 根据宽度和高度即可计算得到该区域能接的雨水量。// 为了得到 left需要将 topp 出栈。在对 top 计算能接的雨水量之后left 变成新的 top
// 重复上述操作直到栈变为空或者栈顶下标对应的 height 中的元素大于或等于 height[i]。// 在对下标 i 处计算能接的雨水量之后将 i 入栈
// 继续遍历后面的下标计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。class Solution {
public:int trap(vectorint height) {int ans 0;stackint stk;int n height.size();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 left stk.top();int currWidth i - left - 1;int currHeight min(height[left], height[i]) - height[top];ans currWidth * currHeight;}stk.push(i);}return ans;}
};// 方法三双指针//维护两个指针 left 和 right以及两个变量 leftMax 和 rightMax
// 初始时 left0,rightn−1,leftMax0,rightMax0。
// 指针 left 只会向右移动指针 right 只会向左移动
// 在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。// 当两个指针没有相遇时进行如下操作// 使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值// 如果 height[left]height[right]则必有 leftMaxrightMax
// 下标 left 处能接的雨水量等于 leftMax−height[left] 处能接的雨水量加到能接的雨水总量
// 然后将 left 加 1即向右移动一位// 如果 height[left]≥height[right]则必有 leftMax≥rightMax
// 下标 right 处能接的雨水量等于 rightMax−height[right]
// 将下标 right 处能接的雨水量加到能接的雨水总量然后将 right 减 1即向左移动一位。// 当两个指针相遇时即可得到能接的雨水总量。class Solution {
public:int trap(vectorint height) {int ans 0;int left 0, right height.size() - 1;int leftMax 0, rightMax 0;while (left right) {leftMax max(leftMax, height[left]);rightMax max(rightMax, height[right]);if (height[left] height[right]) {ans leftMax - height[left];left;} else {ans rightMax - height[right];--right;}}return ans;}
};
