企业官网建设流程全解析

原题链接

分析

首先分析题目：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

也就是计算所有接到的雨水的数量。先竖着看，每次计算一个位置可以保存的雨水，也可以横着看，每次计算一小横行可以存储多少雨水。

1 竖着看

竖着看，一个位置存储的雨水就取决于左右两侧柱子的较小值。
所以只需要计算每个位置左右两侧最大值，然后取出较小值计算就可以了。
那么就使用数组存储就可以，时间复杂度O(n) ，空间复杂度O（n）。
还可以进一步优化，优化空间复杂度到O（1），也就是不提前存储，而是直接每次计算。
使用双指针，同时使用两个数值，记录当前左右两侧最高值。
由于每个位置能够存储的水和两侧最高柱子的较小值有关。那么对于左指针，如果左侧最高值小于右侧，也就是右侧一定更高（右侧可能还有更高的柱子，左侧就是当前确定最大值），两侧中较小值一定是左侧的。那么就可以计算出这个位置可以存储的水量。右侧反之同理。

例如当前位置
l=1,r=11,lmax=1,rmax=2（这里表示高度）
那么就可以确定当前 l 位置存储的水量。

代码

classSolution{public:inttrap(vector<int>&height){intn=height.size();intl=0;intr=n-1;longlongans=0;intlm=0;intrm=0;while(l<r){lm=max(lm,height[l]);rm=max(rm,height[r]);if(lm<rm){ans+=lm-height[l++];}else{ans+=rm-height[r--];}}returnans;}};

横着看

首先注意到，如果能够存储水，柱子的结构应该是凹形的。

使用单调栈，栈底到栈顶存储的柱子高度应该逐渐下降。每次如果遍历的柱子比栈顶高就说明当前形成了一个凹形区域，可以计算当前部分的存储水量，如下：

代码

classSolution{public:inttrap(vector<int>&height){intn=height.size();stack<int>s;longlongans=0;for(inti=0;i<n;i++){while(!s.empty()&&height[i]>height[s.top()]){intm=s.top();s.pop();if(s.empty()){break;}intl=s.top();ans+=(i-l-1)*(min(height[i],height[l])-height[m]);}s.push(i);}returnans;}};