leetcode 42. Trapping Rain Water 谷歌面试题
本帖最后由 Seawolf 于 2019-8-19 06:47 编辑Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array . In this case, 6 units of rain water (blue section) are being trapped.
Example:
Input:
Output: 6
class Solution {
public static int trap(int[] height) {
if(height == null || height.length == 0) {
return 0;
}
int count = 0;
generateNum(height, count);
return count;
}
public static void generateNum(int[] height, int count) {
int len = height.length;
int start = 0,end = 0;
while(start != len && end != len) {
while(height == 0) {
start++;
}
end = start;
end ++;
while(height != 1) {
start++;
}
if(start>0) {
while(end < len && height == 0) {
if(end == len -1 && height != 1) {
end = start;
}
end++;
}
if(end - start >1) {
count = count + end - start - 1;
}
}
while(end < len && height != 1) {
end++;
}
start = end;
todo = false;
}
int ass = 0;
if(start >= len-1 && end >= len-1) {
for(int i = 0; i< len; i++) {
if(height != 0) {
ass = ass+ 1;
height = height - 1;
}
}
if(ass == 1) {
return;
}
else {
ass = 0;
}
generateNum(height,count);
}
}
}
上面这个code虽然可以算出所有的结果，但是交给leetcode 去执行，会报run out of time error 也就是说 efficiency 太差了
下面尝试暴力解法
class Solution {
public static int trap(int[] height) {
int len = height.length;
if(len == 0){
return 0;
}
int ans = 0;
for(int i = 1 ; i < len-1 ; i++){
int leftMax = 0, rightMax = 0;
for(int j = i; j >= 0; j--){
leftMax = Math.max(leftMax, height);
}
for(int m = i; m < len; m ++){
rightMax = Math.max(rightMax,height);
}
ans = ans + Math.min(leftMax,rightMax) - height;
}
return ans;
}
}
虽然通过了pass，但是效率依然是很低，继续改进代码。
class Solution {
public static int trap(int[] height) {
int len = height.length;
if(len == 0){
return 0;
}
int ans = 0;
int[] leftMax = new int;
int[] rightMax = new int;
leftMax = height;
for(int i = 1 ;i <len ; i++ ){
leftMax = Math.max(height, leftMax);
}
rightMax = height;
for(int i = len -2 ;i >=0 ; i-- ){
rightMax = Math.max(height, rightMax);
}
for(int i = 0 ;i< len ; i++ ){
ans = ans + Math.min(rightMax, leftMax) - height;
}
return ans;
}
}
running time 由 O(N^2) 提高到O(N), 继续优化代码，使用双指针进行优化
how it works?
class Solution {
public static int trap(int[] height) {
int ans = 0;
int left_max = 0,right_max = 0;
int left = 0,right = height.length- 1;
while(left < right){
if(height < height){
if(height >= left_max)
left_max = height;
else
ans = ans + left_max - height;
left++;
}
else{
if(height >= right_max)
right_max = height;
else
ans = ans + right_max - height;
right--;
}
}
return ans;
}
}
介绍另外一种方法，使用stack 栈来操作。
class Solution {
public static int trap(int[] height) {
int ans = 0;
int current = 0;
int len = height.length;
Stack <Integer> stack = new Stack<>();
while(current < len){
while(!stack.empty()&& height > height){
int top = stack.peek();
stack.pop();
if(stack.empty()){
break;
}
int distance = current - stack.peek() -1 ;
int bounded = Math.min(height, height) - height;
ans = ans + distance * bounded;
}
stack.push(current++);
}
return ans;
}
}
nice job！！
页:
[1]