马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 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 [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
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[start] == 0) {
start++;
}
end = start;
end ++;
while(height[start] != 1) {
start++;
}
if(start>0) {
while(end < len && height[end] == 0) {
if(end == len -1 && height[end] != 1) {
end = start;
}
end++;
}
if(end - start >1) {
count = count + end - start - 1;
}
}
while(end < len && height[end] != 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[i] != 0) {
ass = ass+ 1;
height[i] = height[i] - 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[j]);
}
for(int m = i ; m < len; m ++){
rightMax = Math.max(rightMax,height[m]);
}
ans = ans + Math.min(leftMax,rightMax) - height[i];
}
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[len];
int[] rightMax = new int[len];
leftMax[0] = height[0];
for(int i = 1 ;i <len ; i++ ){
leftMax[i] = Math.max(height[i], leftMax[i-1]);
}
rightMax[len-1] = height[len - 1];
for(int i = len -2 ;i >=0 ; i-- ){
rightMax[i] = Math.max(height[i], rightMax[i+1]);
}
for(int i = 0 ;i< len ; i++ ){
ans = ans + Math.min(rightMax[i], leftMax[i]) - height[i];
}
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[left] < height[right]){
if(height[left] >= left_max)
left_max = height[left];
else
ans = ans + left_max - height[left];
left++;
}
else{
if(height[right] >= right_max)
right_max = height[right];
else
ans = ans + right_max - height[right];
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[current] > height[stack.peek()]){
int top = stack.peek();
stack.pop();
if(stack.empty()){
break;
}
int distance = current - stack.peek() -1 ;
int bounded = Math.min(height[current], height[stack.peek()]) - height[top];
ans = ans + distance * bounded;
}
stack.push(current++);
}
return ans;
}
}
nice job！！ | 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2019-8-18 13:01:01
置顶卡
千斤顶
显身卡