C++, two pointer solution, 8ms, easy to understand

• ``````class Solution {
public:
int trap(vector<int>& height) {
if(height.size()<=1) return 0;
int i = 0;
int* p = new int[height.size()];//access array is faster than vector, so i copy height to the array
for(i = 0; i<height.size(); i++) p[i] = height[i];
i = 0;
while(!p[i]) i++;
int pointer = i, min = p[i], res = 0;
for(i++; i<height.size(); i++){
if(p[i]<p[pointer]){
if(p[i]>min){
for(int j = i-1; p[j]<p[i]; j--){
res += p[i]-p[j];
p[j] = p[i];
}
}
min = p[i];
}
else{
for(int j = i-1; j>=pointer; j--){
res += p[pointer]-p[j];
}
pointer = i;
}
}
return res;
}
};``````

• c++, 8 ms solution

class Solution {
public:
int trap(vector<int>& height) {

``````    unsigned int len = (unsigned int)height.size();
if(len <= 2)
return 0;

len = len - 1;

int min1 = 0;
int max1 = 0;
int min2 = len;
int max2 = len;

// left side
while(((max1+1) <= len) && (height[max1+1] >= height[max1])) max1++;
min1 = max1;
max1++;

// right side
while( ((max2-1) >=0) && (height[max2-1] >= height[max2])) max2--;
min2 = max2;
max2--;

int water = 0;

while(max1 < max2) {
if(height[min1] <= height[min2]) {
while((max1 <= len) && (max1 < max2) && (height[max1] < height[min1])) {
int value = height[min1] - height[max1];
water += value;
max1++;
}
if(max1 == len) {
break;
}
if(max1 < max2) {
min1 = max1;
max1++;
}
}
else {
while((max2 >= 0) && (max1 < max2) && (height[max2] < height[min2])) {
int value = height[min2] - height[max2];
water += value;
max2--;
}
if(max2 == 0) {
break;
}
if(max2 > max1) {
min2 = max2;
max2--;
}
}
}

int wa =0;
if(max1 == max2) {
wa = max(0,min((height[min1]-height[max1]),(height[min2]-height[max2])));
}
water += wa;
return water;
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.