SHARE
TWEET

Untitled

a guest Sep 17th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.mgtriffid.misc;
  2.  
  3. import java.util.Map;
  4. import java.util.TreeMap;
  5.  
  6. public class Compartment {
  7.  
  8.     public int volume(int[] landscape) {
  9.         TreeMap<Integer, Height> heightMap = new TreeMap<>();
  10.         for (int i = 0, l = landscape.length; i < l; i++) {
  11.             if (!heightMap.containsKey(landscape[i])) {
  12.                 heightMap.put(landscape[i], new Height(i, i, 1));
  13.             } else {
  14.                 final Height height = heightMap.get(landscape[i]);
  15.                 height.area++;
  16.                 height.max = i;
  17.             }
  18.         }
  19.         int volume = 0;
  20.         while (heightMap.size() > 1) {
  21.             final Map.Entry<Integer, Height> highest = heightMap.pollLastEntry();
  22.             Height height = highest.getValue();
  23.             Map.Entry<Integer, Height> nextTallest = heightMap.lastEntry();
  24.             volume += (height.max - height.min - height.area + 1) * (highest.getKey() - nextTallest.getKey());
  25.             final Height next = nextTallest.getValue();
  26.             next.area += height.area;
  27.             next.min = Math.min(height.min, next.min);
  28.             next.max = Math.max(height.max, next.max);
  29.         }
  30.         return volume;
  31.     }
  32.  
  33.     static class Height {
  34.         int min, max, area;
  35.         Height(int min, int max, int area) {
  36.             this.min = min;
  37.             this.max = max;
  38.             this.area = area;
  39.         }
  40.     }
  41. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top