本文共 1858 字，大约阅读时间需要 6 分钟。

class Solution {//O(n)//find the highest bar as one end of the wall//then check left side from left to right, //record the left most high height "h" along the way, //if A[i] < h && A[i] < A[mid], then A[i] contribute h-A[i] water//right side dittopublic:	int trap(int A[], int n) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		if (!A || !n) 			return 0;		int mid = 0, water = 0, h = 0;		for (int i = 0; i < n; ++i) 		{			if (A[i] > A[mid])				mid = i;		}		for (int i = 0; i < mid; ++i)//check left		{			if (h > A[i])				water += h - A[i];			else				h = A[i];		}		h = 0;		for (int i = n - 1; i > mid; --i)//check right		{			if (h > A[i])				water += h - A[i];			else				h = A[i];		}		return water;	}};

second time

class Solution {//stack based solutionpublic:    struct Node    {        int h, len;        Node(int _h = 0, int _len = 0):h(_h), len(_len){};    };    int trap(int A[], int n) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        int areaSum = 0;        stack
   
     S;        S.push(Node(0, 0));        for(int i = 0; i < n; ++i)        {            if(A[i] < S.top().h)            {                 S.push(Node(A[i], 1));                 continue;            }            int curLen = 0;            int heightSum = 0;            while(S.size() > 1 && A[i] >= S.top().h)            {                curLen += S.top().len;                heightSum += S.top().h*S.top().len;                S.pop();            }                       int minHeight = min(S.top().h, A[i]);            int curArea = minHeight*curLen-heightSum;            areaSum += curArea;            if(A[i] > S.top().h)            {                S.pop();                S.push(Node(A[i], 0));            }            else S.push(Node(A[i], curLen+1));        }        return areaSum ;    }};
   

转载地址：http://fhxti.baihongyu.com/