LeetCode_NO42_接雨水
大神的原文地址：
https://blog.****.net/qq_41231926/article/details/82682179
题目描述：
思路一：分别计算每一层能接的雨水数，再逐层累加得到结果（在LeetCode中提交会超时）
首先遍历数组得到最高的柱子的高度maxHeight，我们总共需要计算maxHeight层。
计算第i层时，我们需要将柱子的高度减去i，这里i从0开始计数。我们寻找每一层的左边界left和右边界right，在[left, right]之间高度小于等于0处，我们可以令能接的雨水数加1。
这个思路的时间复杂度很明显，是O(maxHeight * n)级别的，其中n为height数组的长度。而对于空间复杂度，我们使用了一个新的数组newHeight记录各柱子高度减去i时的值，因此是O(n)级别的。
JAVA代码：
public class Solution {
public int trap(int[] height) {
int n = height.length;
int result = 0;
if(n == 0) {
return result;
}
int maxHeight = height[0];
for (int i = 1; i < n; i++) {
if(height[i] > maxHeight) {
maxHeight = height[i];
}
}
int[] newHeight = new int[n];
for (int i = 0; i < maxHeight; i++) {
for (int j = 0; j < n; j++) {
newHeight[j] = height[j] - i;
}
int left = 0;
int right = n - 1;
while(left < n && newHeight[left] <= 0) {
left++;
}
while(right >= 0 && newHeight[right] <= 0) {
right--;
}
for (int j = left; j <= right; j++) {
if(newHeight[j] <= 0) {
result++;
}
}
}
return result;
}
}
思路二：双指针夹逼寻找雨水数
（1）首先，找到能存水的左边界索引left和右边界索引right。
对于左边界索引left是从数组头到数组尾方向看，第一次出现下降趋势的那个索引的位置。
对于右边界索引right是从数组尾到数组头方向看，第一次出现下降趋势的那个索引的位置。
（2）记录左边界和右边界的高度，分别记作leftHeight和rightHeight。显然，雨水数是由较低的边界所决定的。
a.如果leftHeight小于等于rightHeight。
如果此时满足left < right，说明左右边界还没有重合，尝试着令left加1。如果left位置能够存储雨水，则更新结果的值。如果left位置不能存储雨水，说明left位置的高度大于等于leftHeight，这时我们应该进入下一轮循环，更新leftHeight的值。
b.如果leftHeight大于rightHeight
如果此时满足left < right，说明左右边界还没有重合，尝试着令right减1。如果right位置能够存储雨水，则更新结果的值。如果right位置不能存储雨水，说明right位置的高度大于等于rightHeight，这时我们应该进入下一轮循环，更新rightHeight的值。
该思路的时间复杂度是O(n)级别的，空间复杂度是O(1)级别的。
JAVA代码：
public class Solution {
public int trap(int[] height) {
int n = height.length;
int result = 0;
if(n == 0 || n == 1) {
return result;
}
int left = 0;
//variable left represents the left border of the area where can contain water
while(left < n - 1 && height[left + 1] >= height[left]) {
left++;
}
int right = n - 1;
//variable right represents the right border of the area where can contain water
while(right >= 1 && height[right - 1] >= height[right]) {
right--;
}
while(left < right) {
int leftHeight = height[left];
int rightHeight = height[right];
if(leftHeight <= rightHeight) {
while(left < right) {
left++;
if(height[left] < leftHeight) {
result += leftHeight - height[left];
}else {
break;
}
}
}else {
while(left < right) {
right--;
if(height[right] < rightHeight) {
result += rightHeight - height[right];
}else {
break;
}
}
}
}
return result;
}
}
LeetCode解题报告：
思路三：双指针夹逼寻找雨水数的另一种简化形式
在思路二的实现中，对于左边界索引left是从数组头到数组尾方向看，第一次出现下降趋势的那个索引的位置。对于右边界索引right是从数组尾到数组头方向看，第一次出现下降趋势的那个索引的位置。
事实上， 上述步骤完全可以省略不写。因为在循环的判断里已经规定了只有满足height[left] < leftHeight或者height[right] < rightHeight时，才会对结果雨水数result进行更新。这两种情况对于从数组头到数组尾方向或者从数组尾到数组头方向看呈上升趋势或者的索引位置都是不满足要求的。
在循环过程中，如果出现了height[left] >= leftHeight的情况，直接进入下一轮循环更新leftHeight的值，这不是可以简化为直接取height[left]和leftHeight中的较大者作为leftHeight的值吗？对于height[right] >= rightHeight的情况也是同理。本思路就是这样产生的，时间复杂度和空间复杂度均与思路二相同。
JAVA代码：
public class Solution {
public int trap(int[] height) {
int n = height.length;
int result = 0;
if(n == 0 || n == 1) {
return result;
}
int left = 0;
int right = n - 1;
int leftHeight = 0;
int rightHeight = 0;
while(left < right) {
if(height[left] <= height[right]) {
leftHeight = Math.max(leftHeight, height[left]);
result += leftHeight - height[left];
left++;
}else {
rightHeight = Math.max(rightHeight, height[right]);
result += rightHeight - height[right];
right--;
}
}
return result;
}
}
思路四：暴力解法
从整个数组的角度看来，如果找到某一索引i左侧的最大值leftMax，以及索引i右侧的最大值rightMax，就可以知道当前索引i的盛水高度为Math.min(leftMax,rightMax)-height[i]。
由于我们需要对每一索引i都寻求其左侧最大值leftMax和右侧最大值rightMax，因此时间复杂度是O(n ^ 2)级别的，其中n为height数组的长度。空间复杂度是O(1)级别的。
JAVA代码：
public class Solution {
public int trap(int[] height) {
int n = height.length;
int result = 0;
if(n == 0 || n == 1) {
return result;
}
for (int i = 1; i < n - 1; i++) {
int leftMax = 0;
for (int j = 0; j < i; j++) {
leftMax = Math.max(leftMax, height[j]);
}
int rightMax = 0;
for (int j = i + 1; j < n; j++) {
rightMax = Math.max(rightMax, height[j]);
}
int min = Math.min(leftMax, rightMax);
if(min > height[i]) {
result += min - height[i];
}
}
return result;
}
}
思路五：对思路四的改进，空间换时间
在思路四中，我们对于每一个非数组头位置且非数组尾位置的索引i，都寻求其左侧的最大值leftMax，以及右侧的最大值rightMax。
但是其实，从左往右遍历一次数组，可以获得各个区间的leftMax。同理，从右往左遍历可以获得各个区间的rightMax。将这两个值都存在数组中，并对数组进行遍历，计算各个区间的盛水高度。但是这里额外地使用了两个长度为n的数组，其中n为height数组的长度，这体现了程序设计中空间换时间的思想。
时间复杂度是O(n)，空间复杂度也是O(n)。
JAVA代码：
public class Solution {
public int trap(int[] height) {
int n = height.length;
int result = 0;
if(n == 0 || n == 1) {
return result;
}
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = height[0];
rightMax[n - 1] = height[n - 1];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(height[i], leftMax[i - 1]);
rightMax[n - 1 - i] = Math.max(height[n - 1 - i], rightMax[n - i]);
}
for (int i = 1; i < n - 1; i++) {
int min = Math.min(leftMax[i - 1], rightMax[i + 1]);
if(min > height[i]) {
result += min - height[i];
}
}
return result;
}
}
思路六：利用栈对思路一进行改进
在思路一中，我们逐层地计算雨水量，对于每一小块可能存储雨水的地方都是逐个累加的。但是其时间复杂度太高，在LeetCode中不能通过。我们可以利用栈对其作一个改进。
我们的栈stack中存储的是height数组的索引。如果指针cur指向的height数组中的值小于等于栈顶元素或者栈为空，我们就一直入栈，因此我们栈顶元素索引对应的height数组的值是整个栈中最小的。一旦指针cur指向的height数组中的值超过栈顶的元素索引对应的height数组的值，就代表栈顶元素有一个右边界。由于栈中的元素都是递减的，所以如果存在一个比栈顶元素大的栈中元素，则一定可以确定该横向区域内的盛水量。
时间复杂度是O(n)，空间复杂度是O(n)。
JAVA代码：
public class Solution {
public int trap(int[] height) {
int n = height.length;
int result = 0;
if(n == 0 || n == 1) {
return result;
}
int cur = 0;
Stack<Integer> stack = new Stack<Integer>();
while(cur < n) {
while(!stack.isEmpty() && height[cur] > height[stack.peek()]){
int top = stack.pop();
if(stack.isEmpty()){
break;
}
//distance represents the width
int distance = cur - stack.peek() - 1;
//tempHeight represents the height
int tempHeight = Math.min(height[cur], height[stack.peek()]) - height[top];
result += tempHeight * distance;
}
stack.push(cur);
cur++;
}
return result;
}
}