#Problem

#####⭐️⭐️⭐️⭐️⭐️

#Solution

#Solution #1 - Brute Force

对于每个bar, 看它上方是否能够盛水, 方法是找左边最大的和右边最大的.

Time O( N^2 ), Space O(1)

#Solution #2 - Dynamic Programming

找左边最大和右边最大不需要每次都重新遍历来找. 可以通过两个dp数组来存起来.

dpLeft[i] = Math.max(dpLeft[i - 1], height[i]);
dpRight[i] = Math.max(dpRight[i + 1], height[i]);

Time: O(N), Space: O(2*N)

#Solution #3 - Monotonic Stack
  • 和largest rectangle in histogram一样的思路. 只不过histogram是用递增栈, 这道题是使用递减栈.
  • stack里存的也是index.
  • 每次出栈的时候是处理出栈的栈顶元素而非当前元素. 因为每次需要出栈的时候我们可以确定:
    • height[stk.peek()] < height[stk.peek().peek()], stk.peek().peek()意思就是栈顶第二大的元素.
    • height[stk.peek()] < height[i]
#Solution #4 - Two Pointers

还有种O(1) space的two pointers解法. 详见leetcode solution吧. 掌握上面三种方法比较重要.

#Code

#Solution #1 - Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int trap(int[] height) {
int n = height.length;
int res = 0;
for (int i = 0; i < n; i++) {
int leftMax = i;
int rightMax = i;
int l = i, r = i;
while (l >= 0) {
if (height[l] > height[leftMax]) {
leftMax = l;
}
l--;
}
while (r < n) {
if (height[r] > height[rightMax]) {
rightMax = r;
}
r++;
}
res += Math.min(height[leftMax], height[rightMax]) - height[i];
}
return res;
}
}
#Solution #2 - Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] dpLeft = new int[n];
int[] dpRight = new int[n];
for (int i = 0; i < n; i++) {
dpLeft[i] = height[i];
if (i != 0) {
dpLeft[i] = Math.max(dpLeft[i - 1], dpLeft[i]);
}
}
for (int i = n - 1; i >= 0; i--) {
dpRight[i] = height[i];
if (i != n - 1) {
dpRight[i] = Math.max(dpRight[i + 1], dpRight[i]);
}
}
int res = 0;
for (int i = 0; i < n; i++) {
res += Math.min(dpLeft[i], dpRight[i]) - height[i];
}
return res;
}
}
#Solution #3 - Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int trap(int[] height) {
int n = height.length;
Stack<Integer> stk = new Stack<>();
int res = 0;
for (int i = 0; i < n; i++) {
if (stk.isEmpty() || height[i] < height[stk.peek()]) {
stk.push(i);
} else {
while (!stk.isEmpty() && height[i] >= height[stk.peek()]) {
int h = height[stk.pop()];
if (!stk.isEmpty()) {
int len = i - stk.peek() - 1;
res += (Math.min(height[i], height[stk.peek()]) - h) * len;
}
}
stk.push(i);
}
}
return res;
}
}

Comments