程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode][Java] Trapping Rain Water

[LeetCode][Java] Trapping Rain Water

編輯:C++入門知識

[LeetCode][Java] Trapping Rain Water


題意:

 

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.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

\

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. Thanks Marcos for contributing this image!

題目:

給定n個非負整數來代表高度圖,每個欄的寬度為1.計算下雨之後這個東東能最多能盛多少的水。

比如,給定[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個單位。

算法分析:

當刷到這個題的時候我真是醉了。這就是15年春季的阿裡算法工程師實習在線筆試的題目~~

一模一樣,當時水筆的我真心不會做啊,筆試果斷沒過 囧~~

* 觀察下就可以發現被水填滿後的形狀是先升後降的塔形,因此,先遍歷一遍找到塔頂,然後分別從兩邊開始,往塔頂所在位置遍歷,水位只會增高不會減小,

* 且一直和最近遇到的最大高度持平,這樣知道了實時水位,就可以邊遍歷邊計算面積。

* 首先找到最高的,然後從左往最高處掃,

* 碰到一個數A[i],計算A[0,,,i-1]最高的是否高過A[i],

* 如果是,則A[i]上的水的體積為max(A[0...i-1])-A[i],否則為0並且更新最大值

AC代碼:

 

public class Solution 
{
   public int trap(int[] height) 
    {
        if(height==null||height.length==0)
        return 0;
        int res=0;
        int maxvalue=0;
        int label=0;
        int startmvalue=0;
        int endmvalue=0;
        int mtem;
        for(int i=0;imaxvalue)
        	{
        		maxvalue=height[i];
        		label=i;
        	}
        }
        startmvalue=height[0];
        for(int i=0;istartmvalue) startmvalue=height[i];
        	else
        	{
        		res+=startmvalue-height[i];
        	}
        }
        endmvalue=height[height.length-1];
        for(int i=height.length-1;i>label;i--)
        {
        	if(height[i]>endmvalue) endmvalue=height[i];
        	else
        	{
        		res+=endmvalue-height[i];
        	}
        }
    	return res;
    }
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved