Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
twitter water in walls problem
public class WaterBetweenNumberWalls {
public static void main(String[] args) {
int maxStorage = 0;
int[] nums = { 2, 5, 1, 3, 1, 2, 1, 7, 7, 6 };
// int[] nums = { 2, 5, 1, 2, 3, 4, 7, 7, 6 };
// int[] nums = { 2, 5, 1, 2, 3, 4, 7, 5, 6 };
// int[] nums = { 6, 1, 4, 6, 7, 5, 1, 6, 4 };
// int[] nums = { 2, 7, 2, 7, 4, 7, 1, 7, 3, 7 };
maxStorage = GetMaxStorageImprove(nums);
System.out.println(maxStorage);
maxStorage = GetMaxStorage(nums);
System.out.println(maxStorage);
}
public static int GetMaxStorageImprove(int[] nums) {
int count = nums.length;
int leftIndex = 0;
int left = 0;
int rightIndex = 0;
int temp = 0;
int tempIndex = 0;
int right = 0;
int maxStorage = 0;
int storage = 0;
boolean isBreak = false;
// just like pop sort
for (leftIndex = 0; leftIndex < count - 1; leftIndex++) {
// Second one is bigger than first, cannot save water
if (nums[leftIndex + 1] > nums[leftIndex]) {
continue;
}
isBreak = false;
left = nums[leftIndex];
temp = nums[leftIndex + 1];
// max storage for one number
for (tempIndex = leftIndex + 2; tempIndex < count; tempIndex++) {
right = nums[tempIndex];
if (right > temp) {
temp = right;
rightIndex = tempIndex;
if (right > left) {
isBreak = true;
break;
}
}
}
storage = GetStorage(nums, leftIndex, rightIndex);
if (storage > maxStorage)
maxStorage = storage;
// Water in walls between left and right will be smaller
if (isBreak == true) {
leftIndex = rightIndex - 1;
}
}
return maxStorage;
}
public static int GetMaxStorage(int[] nums) {
int count = nums.length;
int leftIndex = 0;
int left = 0;
int rightIndex = 0;
int temp = 0;
int tempIndex = 0;
int right = 0;
int maxStorage = 0;
int storage = 0;
// just like pop sort
for (leftIndex = 0; leftIndex < count - 1; leftIndex++) {
// Second one is bigger than first, cannot save water
if (nums[leftIndex + 1] > nums[leftIndex]) {
continue;
}
left = nums[leftIndex];
temp = nums[leftIndex + 1];
// max storage for one number
for (tempIndex = leftIndex + 2; tempIndex < count; tempIndex++) {
right = nums[tempIndex];
if (right > temp) {
temp = right;
rightIndex = tempIndex;
if (right > left) {
break;
}
}
}
storage = GetStorage(nums, leftIndex, rightIndex);
if (storage > maxStorage)
maxStorage = storage;
}
return maxStorage;
}
public static int GetStorage(int[] nums, int l, int r) {
int storage = 0;
if (nums[r] > nums[l]) {
storage = nums[l] * (r - l - 1);
} else {
storage = nums[r] * (r - l - 1);
}
for (int i = l + 1; i < r; i++) {
storage -= nums[i];
}
return storage;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.