TrapRainWater
这道题目看起来挺复杂的，满足装水的形状就是一个平的子序列，左右都比他大，就可以装水了，但是补了之后，可能还要再补，这是比较麻烦的，尤其是逻辑设计比较纠结。
符合情况的1<=i<=n-2, 因为端点肯定是不能装水的，只有一端拦着。
因此，我先是想了一个多遍扫描，每遍填一层，然后通过一个bool值判断，如果该层没有填就结束了。思路就是首先找符合(a[i-1]>a[i] && a[i]<=a[i+1]),只有这种i才有可能是要填水的起点，
否则直接i++，这里面我现在牢记Knuth说的过早优化是万恶的源头，把else也写出来这样逻辑清晰一点，即使是空语句，尤其是后一种算法不写else根本看不清楚。然后里面再去向后延伸找
最长的一层平的，然后开始填，然后后面对于每一层都这么处理，直到有一次扫描找不到填坑就结束了。
int trap_morepass(int a[], int n)
{
int count=0,i,start;
bool trap;
while(1)
{
i=1;
trap=false;
while(i<=n-2)
{
if(a[i-1]>a[i] && a[i]<=a[i+1])
{
start=i;
while(i<=n-2 && a[i]==a[i+1])
i++;
if(a[i]<a[i+1])
{
count+=(i-start+1)*(min(a[start-1],a[i+1])-a[start]);
trap=true;
for(int j=start;j<=i;j++)
a[j]=min(a[start-1],a[i+1]);
}
else
;
}
else
;
i++;
}
if(trap==false)
break;
}
return count;
}
后来发现TLE了，于是打算优化，上述确实可能很慢，极端情况扫描次数可能是里面max(a[i]),于是优化着眼点还是把里面的多遍扫描变成一遍，也就是填了水之后，就地在这基础上再看是否
需要填水，因此if改成while，如果填了水之后，左端可能会延伸，如果延伸后降了，就不能再填水了，否则需要处理，这里while将i跳到j，也即新的可能的
填水的起点，代码依然不优化，把else留着，这样逻辑结构非常清晰。
int trap_onepass(int a[], int n)
{
int count=0,i,start,j;
bool trap;
//while(1)
//{
i=1;
// trap=false;
while(i<=n-2)
{
while(a[i-1]>a[i] && a[i]<=a[i+1])
{
start=i;
while(i<=n-2 && a[i]==a[i+1])
i++;
if(a[i]<a[i+1])
{
count+=(i-start+1)*(min(a[start-1],a[i+1])-a[start]);
//trap=true;
for(j=start;j<=i;j++)
a[j]=min(a[start-1],a[i+1]);
j=start;
while(j>=1 && a[j-1]==a[j])
j--;
if(j>=1)
{
if(a[j-1]>a[j])
i=j;
else
break;
}
else
;
}
else
;
}
//else
// ;
i++;
}
// if(trap==false)
// break;
//}
return count;
}
本地测试最大的数据10732大小数组， 时间从2s降到1s，但可惜的是还是TLE了，暂时放一放。。。。
坑爹，发现里面count+ 和a[j]需要重新附上填坑后的值，于是发现之前的语句错了，要找两端较小的，所以Leetcode很多TLE其实是WA，但是即使这样有一个简单的case过不了，[4,2,3], 明明本地是输出1的，OJ输出了3，不知道
为啥。。。
后来搞了半天，代码漏掉一个越界处理，于是乎发现了VC和GCC的区别了，两者对于数组越界都不报错，这是访问了一个野值而已，而VC野值是一个很大的正数，GCC是负数，因此到了if(a[i]<a[i+1])时，
VCtrue，GCCfalse了，主要是上面while有两个条件与，因此每个条件结束循环都要处理。。附上AC代码。。。
class Solution {
public:
int trap(int a[], int n)
{
int count=0,i,start,j;
bool trap;
//while(1)
//{
i=1;
// trap=false;
while(i<=n-2)
{
while(a[i-1]>a[i] && a[i]<=a[i+1])
{
start=i;
while(i<=n-2 && a[i]==a[i+1])
i++;
//if(i>n-2) break;
if(a[i]<a[i+1])
{
count+=(i-start+1)*(min(a[start-1],a[i+1])-a[start]);
//trap=true;
for(j=start;j<=i;j++)
a[j]=min(a[start-1],a[i+1]);
j=start;
while(j>=1 && a[j-1]==a[j])
j--;
if(j>=1)
{
if(a[j-1]>a[j])
i=j;
else
break;
}
else
;
}
else
;
}
//else
// ;
i++;
}
// if(trap==false)
// break;
//}
return count;
}
};