代码拉取完成,页面将自动刷新
package code;
import java.util.Stack;
/*
* 42. Trapping Rain Water
* 题意:能盛多少水
* 难度:Hard
* 分类:Array, Two Pointers, Stack
* 思路:三种方法:1.DP先求出来每个位置的maxleft,maxright,再遍历一遍;2.两个指针,类似lc11题的思路;3.用栈数据结构;
* Tips:lc11, lc42, lc84
*/
public class lc42 {
public static void main(String[] args) {
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(trap(height));
System.out.println(trap2(height));
}
public static int trap(int[] height) {
if(height.length<3)
return 0;
int left = 0;
int right = height.length-1;
int res =0;
while(left<right){
if(height[left]<height[right]){
int edge_l = height[left];
left++;
while(height[left]<edge_l && left<right){
if(edge_l-height[left]>0)
res += edge_l-height[left];
left++;
}
}else if(height[left]>=height[right] && left<right){
int edge_r = height[right];
right--;
while(height[right]<edge_r){
if(edge_r-height[right]>0)
res += edge_r-height[right];
right--;
}
}
}
return res;
}
public static int trap2(int[] A) {
//栈方法
if (A==null) return 0;
Stack<Integer> s = new Stack<Integer>();
int i = 0, maxWater = 0, maxBotWater = 0;
while (i < A.length){
if (s.isEmpty() || A[i]<=A[s.peek()]){
s.push(i++); //递减栈
}
else {
int bot = s.pop();
maxBotWater = s.isEmpty()? // empty means no il
0:(Math.min(A[s.peek()],A[i])-A[bot])*(i-s.peek()-1);
maxWater += maxBotWater;
}
}
return maxWater;
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。