网络专题策划模板_快速开发安卓app_引擎搜索有哪些_梅花seo 快速排名软件

1、 题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

2、解题思路

2.1 双指针

本题使用了双指针，根据下图可以得出，下标 i 处能接的雨水量由左边最大值 leftMax 和右边最大值 rightMax 中的最小值决定，因此设置左指针left和右指针right，左指针只会向右移动，右指针只会向左移动，遍历的过程中持续更新 leftMax 和 rightMax 。

• 若 leftMax < rightMax，下标 left 处能接的雨水量等于 leftMax−height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）
• 若 leftMax ≥ rightMax，下标 right 处能接的雨水量等于 rightMax−height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 1（即向左移动一位）

class Solution {public int trap(int[] height) {// 定义左右指针int left=0,right=height.length-1;// 定义左边最大值和右边最大值int leftMax=0,rightMax=0;// 定义最终结果int ans = 0;// 两个指针相遇为循环结束条件while(left<right){// 判断当前高度是否比最大高度大，若是，更新最大高度if(height[left]>leftMax)leftMax = height[left];if(height[right]>rightMax)rightMax = height[right];// 下标i处能接到的雨水量由leftMax和rightMax的最小值决定if(leftMax<rightMax){ans += leftMax-height[left];left++;}else{ans += rightMax-height[right];right--;}}return ans;}
}

• 时间复杂度：O(n)，其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。
• 空间复杂度：O(1)。只需要使用常数的额外空间。

2.2 单调递减栈

根据题意可知，若当前的柱子比前面的柱子低，那么当前柱子就可能存到水，故使用递减栈。使用递减栈可以确保非栈顶柱子高度比栈顶柱子高，即确保了左边界，而若遍历过程中遇到比栈顶高的柱子，即右边界，那么栈顶柱子必能存到水。

class Solution {public int trap(int[] height) {// 创建递减栈，存储下标，从栈底到栈顶递减int len = height.length,ans=0;// 创建栈Deque<Integer> stack = new ArrayDeque<>(len);for(int i=0;i<len;i++){// 当前柱子高度比栈顶的柱子高while(!stack.isEmpty() && height[i]>height[stack.peek()]) {// 得到栈顶的柱子高度并将其弹出，若弹出后栈为空仍不影响结果，因为后面的柱子比它高int top = height[stack.pop()];if(stack.isEmpty())break;// 得到现在栈顶的柱子高度，也就是原来栈顶柱子的左边柱子// 左右两边的柱子都比原来栈顶柱子高，因此能够积水int left = height[stack.peek()];// 左右两边柱子的最小值 * 宽度ans += (Math.min(left, height[i])-top) * (i-stack.peek()-1);    	}// 注意这里存储的是下标stack.push(i);}return ans;}
}

• 时间复杂度：O(n)，其中 n 是数组 height 的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。
• 空间复杂度：O(n)，其中 n 是数组 height 的长度。空间复杂度主要取决于栈空间，栈的大小不会超过 n。