面试经典150题—

面试经典150题——接雨水

面试经典150题 day16

- - 题目来源
  - 我的题解
  - - 方法一暴力解法
    - 方法二备忘录优化
    - 方法三双指针
    - 方法四单调栈

题目来源

力扣每日一题；题序：42

我的题解

方法一暴力解法

计算每一个位置的水有多少。找到每个位置的左侧最大值和右侧最大值，然后取两者中的较小的(水桶装水原理)，如果较小的大于当前位置，则表示该位置可以接雨水，接雨水的量：min(leftMax,rightMax)-cur
以前是能过的，现在好像过不了了

时间复杂度：O( $n^2$ )
空间复杂度：O(1)

class Solution {
    public  int trap(int[] height) {
        int res=0;
        for(int i=1;i<height.length-1;i++){
        	//左侧最大值的位置
	        int left=findMax(height,0,i);
	        //右侧最大值的位置
	        int right=findMax(height,i,height.length);
	        //两者中的较小值
	        int min=Math.min(height[left],height[right]);
	        if(min>=height[i])
	            res+=min-height[i];
        }
        return res;
    }
	//找最大值所在位置
    private  int findMax(int[] height, int s, int e) {
        int max=height[s];
        int index=s;
        for(int i=s;i<e;i++){
	        if (height[i] > max) {
	            max=height[i];
	            index = i;
	        }
        }
        return index;
    }
}

方法二备忘录优化

在方法一中求左侧和右侧的最大值都会重复计算，因此可以提前预先计算每个位置的左侧和右侧最大值

时间复杂度：O(n)
空间复杂度：O(n)

public  int trap(int[] height) {
    int res=0;
    int n=height.length;
    int[] left=new int[n];
    int[] right=new int[n];
    left[0]=height[0];
    right[n-1]=height[n-1];
    for(int i=1;i<n;i++)
        left[i]=Math.max(left[i-1],height[i]);
    for(int i=n-2;i>=0;i--)
        right[i]=Math.max(right[i+1],height[i]);
    for(int i=1;i<height.length-1;i++){
        int min=Math.min(left[i],right[i]);
        res+=min-height[i];
    }
    return res;
}

方法三双指针

两个指针分别指向还未被遍历的最左侧和最右侧，然后依次遍历每个位置，leftMax和rightMax不再是当前位置左侧和右侧的最大值，而是[0,left]和[right,end]中的最大值。

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
  public static int trap(int[] height) {
    int res=0;
    int left=0,right=height.length-1;
    int leftMax=height[left],rightMax=height[right];
    while(left<right){
      if(height[left]<height[right]){
        //找左边最大
        if(height[left]>leftMax)
          leftMax=height[left];
        else
          res+=leftMax-height[left];
        left++;
      }else{
        //找右边最大
        if(height[right]>rightMax)
          rightMax=height[right];
        else
          res+=rightMax-height[right];
        right--;
      }
    }
    return res;
  }
}

方法四单调栈

该方法计算雨水量是横向计算每个水平面可以接的雨水量。
用单调栈计算能接的雨水总量。维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。
从左到右遍历数组，遍历到下标 iii 时，如果栈内至少有两个元素，记栈顶元素为 top，top 的下面一个元素是 left，则一定有 height[left]≥height[top]。如果 height[i]>height[top]，则得到一个可以接雨水的区域，该区域的宽度是 i−left−1，高度是 min⁡(height[left],height[i])−height[top]，根据宽度和高度即可计算得到该区域能接的雨水量。
为了得到 left，需要将 top 出栈。在对 top 计算能接的雨水量之后，left 变成新的 top，重复上述操作，直到栈变为空，或者栈顶下标对应的 height中的元素大于或等于 height[i]。
在对下标 i 处计算能接的雨水量之后，将 i 入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
  public static int trap(int[] height) {
    int res=0;
    Stack<Integer> stack=new Stack<>();
    int i=0;
    while(i<height.length){
      while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
        int low=stack.pop();
        if(stack.isEmpty())
          break;
        int min=Math.min(height[stack.peek()],height[i]);
        int width=i-stack.peek()-1;
        res+=width*(min-height[low]);
      }
      stack.push(i++);
    }
    return res;
  }
}