新农上路
- 积分
- 99
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2011-11-22
- 最后登录
- 1970-1-1
|
本帖最后由 yjyongz 于 2011-12-11 07:04 编辑
Space Complexity is constant
Time Complexity is O(N)
- public class Calculate_Volumn {
-
- public static int scanFoward(int array[]){
- if(array.length <=2) return 0;
- int volumn = 0;
- for(int i=0,adv=1;i<array.length;){
- if(array[i]!=0){
- adv = i;
- int count = 0;
- while(true){
- adv++;
- if(adv < array.length - 1&&array[adv] < array[i])
- count+=array[adv];
- else break;
- }
- if(adv < array.length&&array[adv] >= array[i]){
- int height = array[i];
- int dist = adv - i - 1;
- volumn += height * dist - count;
- }
- i = adv;
- }else{
- i++;
- }
- }
- return volumn;
- }
-
- public static int scanBackward(int array[]){
- if(array.length <=2) return 0;
- int volumn = 0;
- for(int i=array.length-1,adv=array.length-2;i>=0;){
- if(array[i]!=0){
- adv = i;
- int count = 0;
- while(true){
- adv--;
- if(adv >=0 &&array[adv] < array[i])
- count+=array[adv];
- else break;
- }
- if(adv>=0&&array[adv]>=array[i]){
- int height = array[i];
- int dist = i - adv - 1;
- volumn += height * dist - count;
- }
- i = adv;
- }else{
- i--;
- }
- }
- return volumn;
- }
-
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- try{
- int array[] = {0,1,0,2,1,0,1,3,2,1,2,1};//it should be 6
- int array_1[] = {0,1,0,2};//it should be 1
- int array_2[] = {0,1,0,2,1,0,1,3};//it should be 5
- int array_3[] = {0,1};//it should be 0
- int array_4[] = {5,4,3,2,1};//it should be 0
- int array_5[] = {1,2,3,4,5};//it should be 0
- int volumn = 0;
-
- Object obj[] = {array,array_1,array_2,array_3,array_4,array_5};
- for(int i=0;i<obj.length;i++){
- array = (int[])obj[i];
- // O(N)--forward
- volumn = scanFoward(array);
- // O(N)--backward
- volumn += scanBackward(array);
- System.out.println(volumn);
- }
- }catch(Exception e){
- e.printStackTrace();
- }
- }
- }
复制代码 |
|