接雨水【Leecode 42】（坐标轴上的故事)

题目：

考场思路：

1. 见到n的范围有1e4，O(n^2)勉强能过。
2. 然后分析：
   1> 对于任意两柱子，其之间的积水体积= min_height(柱子a,柱子b)*(b-a-1) - 两柱子间所有柱子的体积和
   2> 这两个柱子该如何取？（可形成积水的两个柱子的条件）：
   情况1： left为起点向后遍历，第一个>=自己的柱子作为right
   情况2： 如果没有比自己高的，则从那些比自己低的柱子里，取最高的right
   每次left都取上一个right，如果上一left没有合法right，则left++
   (换句话说，比自己高的，那就近原则；没有比自己好的，那就找最好的备胎

class Solution {
public:
    int query_V(int *p,int a,int b){//操作1> 求任意两柱子中间的面积
        int res=0;
        for(int i=a+1;i<b;i++) res+=*(p+i);
        return min( *(p+a),*(p+b) )*(b-a-1)-res;
    }
    int trap(vector<int>& height) {
        int n=height.size();if(n==1) return 0;//特判
        int left=0,ans=0;height.push_back(0);
        while(left<n && height[left]==0 ) left++;//前置0存不住水，直接跳过
        while(left<n ) {
            int right,minx_id=n;
            for(right=left+1;right<n;right++)
            if(height[right]>=height[left]){//情况1
                ans+=query_V( &height[0],left,right);
                break;
            }else if(height[right]>=height[minx_id]) minx_id=right;//情况2
        
            if(right<n ) left=right;//有大于自己的right
            else if(height[minx_id]!=0){//没有比自己大的，就去选最好的备胎
                ans+=query_V(&height[0],left,minx_id);
                left=minx_id;
            }else left++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

显然…这暴力方法是我自己造得，感觉很蠢，而且这种坐标轴上的题，总是会有很巧妙的方法，所以看了一眼人家的做法。

优化思路：

1. 坐标轴上的故事，当然尽量想O(n)了
2. 然后分析：
   1>对于任意一个下标 id 处的空间，其可存水的体积如何计算？如果可以O(1)计算这个体积，那我们就可以实现O(n)计算答案
   2> id左边最高的柱子 和 id右边最高的柱子 构成了id所对应的积水空间，则 V [ id ] = min( L_max, R_max） *1
   3> L_max 和 R_max， O(n)扫描处理
   即三个O(n) 实现上述思路

const int N=2e4+10;
#define h height
#define n height.size()
class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0,r[N],l[N];l[0]=h[0];r[n-1]=h[n-1];
        for(int i=n-2;i>=0;i--) r[i]=max(r[i+1],h[i]);
        for(int i=1;i<n;i++) l[i]=max(l[i-1],h[i]);
        for(int i=0;i<n;i++) ans+=max(min(l[i],r[i])-h[i],0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

巧妙！