twitterm面试算法题
“看下面这个图片”
“在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表，数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6]”
“假如开始下雨了，那么墙之间的水坑能够装多少水呢？”
“以1×1的方块为单位计算容积。所以，在上边的图中下标为1以左的都会漏掉。下标7以右的也会漏掉。剩下的只有在1和6之间的一坑水，容积是10”
分析：直观看上去这题的一种思路就是遍历一遍数组找到数组的最大值和第二大的值，计算出他们之间的积水值，然后递归计算出他们两边的的最大值和二大值，计算出他们的积水值，这样递归下去得到最后的结果。这种算法的最坏时间复杂度是O(n^2)。
还有一种非常简单的思路只用O(n)时间就可以计算出来，这种算法的思路是：设置两个指针，分别从左向右遍历和从右向左遍历，直到两个指针相遇，现在只先说从左往右的情况，从右往左的情况是一样的，开始是分别设置左边的最大值和右边的最大值，如果左边的最大值大则，左边的指针向前移动，然后比较此时指针的值，具体见如下代码：
#include<iostream>#include<vector>using namespace std;int main(void){vector<int> height;int n;cin>>n;int a;for(int i = 0;i < n;i++){cin>>a;height.push_back(a);}vector<int>::iterator it_l = height.begin();vector<int>::iterator it_r = height.end() - 1;int max_l = *it_l, max_r = *it_r;int cou = 0;while(it_l < it_r){if(max_l < max_r){it_l++;if(*it_l > max_l){max_l = *it_l;}elsecou += max_l - *it_l;}else{it_r--;if(*it_r > max_r){max_r = *it_r;}elsecou += max_r - *it_r;}}cout<<cou<<endl;cin>>cou;return 0;}