宁波网站建设 首选智尚网络,建设项目安监备案网站,上海市质量工程建设管理协会网站,设计 在线目录 题目1- 思路2- 实现⭐42. 接雨水——题解思路 3- ACM实现 题目
原题连接#xff1a;42. 接雨水 1- 思路
模式识别#xff1a;求雨水的面积 —— 不仅是只求一个比当前元素大的元素#xff0c;还要求面积
单调栈
应用场景#xff0c;需要找到左边比当前元素大的… 目录 题目1- 思路2- 实现⭐42. 接雨水——题解思路 3- ACM实现 题目
原题连接42. 接雨水 1- 思路
模式识别求雨水的面积 —— 不仅是只求一个比当前元素大的元素还要求面积
单调栈
应用场景需要找到左边比当前元素大的元素
单调栈实现
当前元素和栈口元素作比较如果当前元素大于栈口元素此时收集结果例如 栈口元素是 10如果当前元素是 30 此时找到 元素 10 右侧第一个比 它大的元素值是 30右侧第一个比他大的元素是 栈里的第二个元素
单调栈的维护
单调栈与当前元素存在三种情况① 等于、②小于、③大于。要用单调栈来存储遍历过的元素 如果小于等于 栈口元素此时直接入栈如果大于栈口元素此时收集结果 ①凹槽底部元素int mid st.top(); st.pop();②计算水高int h Math.min(st.top(),height[i])-height[mid]; 从右侧柱高和左侧柱高取个最小值③计算雨水面积宽度int width i - st.pop() - 1;④计算面积area h * width; 2- 实现
⭐42. 接雨水——题解思路 class Solution {public int trap(int[] height) {int sum 0;if(height.length 0){return 0;}// 定义栈StackInteger st new StackInteger();st.push(0);for(int i 1 ; i height.length;i){if(height[i] height[st.peek()]){st.push(i);}else{while(!st.isEmpty() height[i] height[st.peek()]){int mid st.peek();st.pop();if(!st.isEmpty()){int h Math.min(height[st.peek()],height[i]) - height[mid];int width i-st.peek() - 1; int hold h*width;sumhold;}}st.push(i);}}return sum;}
}3- ACM实现
public class getRain {public static int getRain(int[] nums){// 定义单调栈int len nums.length;if(len0){return 0;}int sum 0;StackInteger st new Stack();st.push(0);for(int i 1 ; i len;i){if(nums[i]nums[st.peek()]){st.push(i);}else{while(!st.isEmpty() nums[i] nums[st.peek()]){int mid st.peek();st.pop();if(!st.isEmpty()){int h Math.min(nums[st.peek()],nums[i])-nums[mid];int width i - st.peek()-1;int hold h*width;sumhold;}}}st.push(i);}return sum;}public static void main(String[] args) {// 计算Scanner sc new Scanner(System.in);System.out.println(输入数组长度);int n sc.nextInt();int[] nums new int[n];for(int i 0 ; i n ; i ){nums[i] sc.nextInt();}System.out.println(雨水面积是getRain(nums));}
}
