Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Example：
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
解釋下題目：
就是給一個數(shù)組彤灶，這個數(shù)組對應(yīng)矩形的條(圖中的黑色)谜疤，然后看這些條組成的能裝多少“雨水”，圖中的藍(lán)色部分。
1. 自己的騷操作
實際耗時：沒通過
public int trap(int[] height) {
List<Integer> list = new ArrayList<>();
int start = 0;
while (-1 != (start = findHighest(height, start))) {
list.add(start);
start++;
}
System.out.println(list);
int[] array = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
array[i] = list.get(i);
}
int result = 0;
int left = 0;
int right = 0;
for (int i = 0; i < array.length - 1; i++) {
if (array[i] + 1 == array[i + 1]) {
left = i;
continue;
} else {
//計算
right = i + 1;
result += calculateTwoColumn(height, array[left], array[right]);
}
}
return result;
}
public int findHighest(int[] height, int start) {
while (height.length > start + 1) {
if (height[start + 1] >= height[start]) {
start++;
} else {
return start;
}
}
return -1;
}
public int calculateTwoColumn(int[] height, int start, int end) {
int wid = end - start - 1;
int high = Math.min(height[start], height[end]);
int exist = 0;
for (int i = start + 1; i < end; i++) {
exist += height[i];
}
return wid * high - exist;
}
??我之前的思路是，找到局部最高的那些條，然后計算即可宇立。后來發(fā)現(xiàn)就算是局部最長的條，也可能被其他的更長的條給包圍自赔，所以出現(xiàn)了錯誤妈嘹。
時間復(fù)雜度O(n)
空間復(fù)雜度O(1)
2. 暴力破解
實際耗時：97ms
代碼比較簡單就黏貼過來了
public int trap2(int[] height) {
int result = 0;
int size = height.length;
for (int i = 1; i < size - 1; i++) {
int max_left = 0, max_right = 0;
for (int j = i; j >= 0; j--) { //Search the left part for max bar size
max_left = Math.max(max_left, height[j]);
}
for (int j = i; j < size; j++) { //Search the right part for max bar size
max_right = Math.max(max_right, height[j]);
}
result += Math.min(max_left, max_right) - height[i];
}
return result;
}
??思路很簡單，針對每一個柱匿级，如果它上面能放雨水蟋滴，那么必然有它的左邊和它的右邊有比它還高的柱子，找到左右兩邊最高(可能是自己)的痘绎，然后找出其中比較矮的那根津函，減去它自己就是它所能存放的雨水。
時間復(fù)雜度O(n^2)
空間復(fù)雜度O(1)
3. 使用動態(tài)規(guī)劃
實際耗時：13ms
public int trap3(int[] height) {
int len = height.length;
if (0 == len) {
return 0;
}
int[] left = new int[len];
int[] right = new int[len];
left[0] = height[0];
right[len - 1] = height[len - 1];
int left_max = height[0];
int right_max = height[len - 1];
int result = 0;
//按照從左到右遞增的順序填充數(shù)組孤页，并記錄填充的大小
for (int i = 1; i < len; i++) {
if (height[i] <= left_max) {
left[i] = left_max;
} else {
left_max = height[i];
left[i] = left_max;
}
}
//按照從右到左遞增的順序填充數(shù)組尔苦，并記錄填充的大小
for (int i = len - 2; i >= 0; i--) {
if (height[i] <= right_max) {
right[i] = right_max;
} else {
right_max = height[i];
right[i] = right_max;
}
}
//計算重疊部分
for (int i = 0; i < len; i++) {
result += Math.min(left[i] - height[i], right[i] - height[i]);
}
return result;
}
??按照從左到右遞增的方式“補(bǔ)全”數(shù)組，然后按照從右到左的方式“補(bǔ)全”數(shù)組行施，這兩個重疊的部分就是所求的解允坚。
