三刷 07/2022
Version #4 Two Pointers
Time O(N)
Space O(1)
Runtime: 2 ms, faster than 56.76% of Java online submissions for Trapping Rain Water.
Memory Usage: 49 MB, less than 33.16% of Java online submissions for Trapping Rain Water.
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int sum = 0;
// l r
// [2, 1, 3, 1, 4]
while (left <= right) {
if (height[left] < height[right]) {
if (height[left] > leftMax) {
leftMax = height[left];
} else {
sum += leftMax - height[left];
}
left++;
} else {
if (height[right] > rightMax) {
rightMax = height[right];
} else {
sum += rightMax - height[right];
}
right--;
}
}
return sum;
}
}
Version #3 Two Passes Iteration
Time O(N)
Space O(N)
Runtime: 2 ms, faster than 56.76% of Java online submissions for Trapping Rain Water.
Memory Usage: 48.9 MB, less than 33.16% of Java online submissions for Trapping Rain Water.
class Solution {
public int trap(int[] height) {
int[] right = new int[height.length];
int r = 0;
for (int i = height.length - 1; i >= 0; i--) {
right[i] = r;
if (height[i] > r) {
r = height[i];
}
}
int l = 0;
int sum = 0;
for (int i = 0; i < height.length; i++) {
if (Math.min(l, right[i]) > height[i]) {
sum += Math.min(l, right[i]) - height[i];
}
if (height[i] > l) {
l = height[i];
}
}
return sum;
}
}
Version #2 Stack - better
Time O(N)
Space O(N)
Runtime: 16 ms, faster than 10.10% of Java online submissions for Trapping Rain Water.
Memory Usage: 49.6 MB, less than 10.71% of Java online submissions for Trapping Rain Water.
class Solution {
public int trap(int[] height) {
Stack<Integer> stack = new Stack<>();
int sum = 0;
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
int bottom = height[stack.pop()];
if (stack.isEmpty()) {
break;
}
sum += (Math.min(height[i], height[stack.peek()]) - bottom) * (i - stack.peek() - 1);
}
stack.push(i);
}
return sum;
}
}
Version #1 Stack - naiive
100%自己写的方法，维护一个bottom表示之前fill到的height，每次pop出前一个比自己小的height然后从bottom fill到height
这个方法一开始写了bug就是当当前点低于前一个element的时候也是可以fill的，譬如
4, 2, 0, 3, 2, 5 在走到3的时候如果只pop到2就是不对的，要一直看到4但是不把4pop出来
看到之前的写法是看stack里面的两个值，一个作为bottom，一个作为left
Time O(N)
Space O(N)
Runtime: 26 ms, faster than 5.92% of Java online submissions for Trapping Rain Water.
Memory Usage: 49.1 MB, less than 24.21% of Java online submissions for Trapping Rain Water.
class Solution {
public int trap(int[] height) {
int sum = 0;
// Monotonic decreasing stack of the indices
Stack<Integer> stack = new Stack<>();
int bottom = 0;
for (int i = 0; i < height.length; i++) {
if (stack.isEmpty() || height[i] < height[stack.peek()]) {
stack.push(i);
continue;
}
// current height is larger than the element in the stack
while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
int left = stack.pop();
// System.out.printf("=>left=%d,height[left]=%d, bottom=%d, i=%d\n",left, height[left], bottom, i);
sum += (height[left] - bottom) * (i - left - 1);
bottom = height[left];
}
if (!stack.isEmpty() && height[stack.peek()] > height[i]) {
int left = stack.peek();
// System.out.printf("left=%d,height[left]=%d, bottom=%d, i=%d\n",left, height[left], bottom, i);
sum += (height[i] - bottom) * (i - left - 1);
bottom = height[i];
}
stack.push(i);
if (stack.isEmpty()) {
bottom = 0;
}
}
return sum;
}
}
二刷
Keep track of the left height of each base
Fill the water layer by layer
Time O(n)
Space O(n)
22.32 %
class Solution {
public int trap(int[] height) {
// a hight of a col is defined by min(leftMax, rightMax)
// keep a descreasing stack of index
Stack<Integer> stack = new Stack<>();
// stack of indexes
// if coming bar is higher than height[stack.peek()], h = Math.min(left, right) - stack.peek()
// width = right - left - 1
// stack 1 3
// 0 1 2 3 4 5 6 7 8 9 10 11
// i
// [0,1,0,2,1,0,1,3,2,1,2,1]
int sum = 0;
for (int i = 0; i < height.length; i++) {
int rHeight = height[i]; // 2
while (!stack.isEmpty() && height[stack.peek()] < rHeight) {
int base = height[stack.pop()];
if (!stack.isEmpty()) {
int lHeight = height[stack.peek()];
sum += (Math.min(lHeight, rHeight) - base) * (i - stack.peek() - 1);
}
}
stack.push(i);
}
return sum;
}
}
一刷
public class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) return 0;
int leftMax = 0;
//stack of indicies of bars need to be calculated
Stack<Integer> stack = new Stack<>();
int sum = 0;
int index = 0;
while (index < height.length) {
if (stack.isEmpty() || height[index] < height[stack.peek()]) {
stack.push(index);
//System.out.println("stack" + stack.peek());
index++;
} else {
int bottom = height[stack.pop()];
//System.out.println("bottom" + bottom);
if (!stack.isEmpty()) {
int left = height[stack.peek()];
sum += (Math.min(left, height[index]) - bottom) * (index - stack.peek() - 1);
//System.out.println(Math.min(left, height[index]));
}
}
}
return sum;
}
}
Version #2 Two pointers
public class Solution {
/**
* @param heights: an array of integers
* @return: a integer
*/
public int trapRainWater(int[] heights) {
// write your code here
if (heights == null || heights.length < 3) return 0;
int sum = 0;
int left = 0, right = heights.length - 1;
int leftMax = heights[left];
int rightMax = heights[right];
while (left + 1 < right) {
//start to fill from the left side
if (leftMax < rightMax) {
left++;
if (heights[left] >= leftMax) leftMax = heights[left];
else {
sum += leftMax - heights[left];
}
//start to fill from the right side
} else {
right--;
if (heights[right] >= rightMax) rightMax = heights[right];
else {
sum += rightMax - heights[right];
}
}
}
return sum;
}
}
Version #3 1Pointer 2Pass
Scan from left to right to get the maxLeft array
Then scan back from right to left to get the maxRight array and calculate the volume at the same time
Time O(n) 2pass
Space O(n)
38.90 %
public class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) return 0;
int[] left = new int[height.length];
int maxLeft = 0;
for (int i = 0; i < height.length; i++) {
left[i] = maxLeft;
maxLeft = Math.max(maxLeft, height[i]);
}
int sum = 0;
int maxRight = 0;
for (int j = height.length - 1; j >= 0; j--) {
//min(maxLeft, maxRight)
int volume = Math.min(left[j], maxRight) - height[j];
if (volume > 0) sum += volume;
maxRight = Math.max(height[j], maxRight);
}
return sum;
}
}
No comments:
Post a Comment