石河子网站建设,重庆网站建设推广,excel做网站数据库,wordpress換域名LeetCode 42. 接雨水
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
示例#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出#xff1a;6 解释#xff1a;上面是由数…LeetCode 42. 接雨水
题目描述
给定 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[下标]就可以获得下标处高度
当height[栈顶下标]height[当前下标]时将当前下标压入栈中此时是后面的高度前面的高度当height[栈顶下标]height[当前下标]时弹出栈顶下标压入当前下标虽然不弹出就压入也不影响计算但是因为相同高度没法存水可以通过这个操作避免重复计算当height[栈顶下标]height[当前下标]时就到了计算存水面积的时候了这里需要不断弹出那些小的元素。那么储水高度heightMath.min(height[栈顶下标的left],height[栈顶下标的right])-height[栈顶下标] 就相当于把栈顶的高度作为底左右围在一起形成一个容器。储水宽度width栈顶下标的right-栈顶下标的left-1。最终面积sumh*w。
代码
class Solution {public int trap(int[] height) {// 根据卡神单调栈版写的int size height.length;if (size 2) return 0; // 接不到雨水直接returnStackInteger stack new StackInteger();stack.push(0);int sum 0;for (int i 1; i height.length; i) {int stackTop stack.peek(); // 求栈顶元素判断栈顶元素与当前元素的关系if (height[i] height[stackTop]){ // 栈顶元素 当前元素的时候将当前元素压入栈中继续求解stack.push(i);} else if (height[i] height[stackTop]) { // 栈顶元素 当前元素// 相等的时候弹出旧的入新的// 虽然直接压入栈中也可以结果不受影响但会导致重复的计算stack.pop();stack.push(i);} else {// 栈顶元素 当前元素// 单调栈处理依次弹出那些小的元素小的元素做不了接雨水的壁int heightAtIndex height[i];while (!stack.isEmpty() heightAtIndex height[stackTop]){int mid stack.pop();if (!stack.isEmpty()){int left stack.peek();int h Math.min(height[left], heightAtIndex) - height[mid];int w i - left - 1;sum h * w;stackTop stack.peek();}}stack.push(i);}}return sum;}
}
