LeetCode 42. Trapping Rain Water

Python解法

解题思路：

本思路需找到最高点左右遍历，时间复杂度O（nlogn），以下为向左遍历的过程。

将每一个点的高度和索引存成一个元组 (val, idx)找到最高的点（可能有多个，任取一个），记为 (now_val, now_idx)。向左找第一个val不大于now_val的点(left_val, left_idx)。以left_val作为水平面，用height[left_val+1, now_val-1]中每一个点更新ans。now_val, now_idx = left_val, left_idx。如果now_idx >= 0 ，重复执行3；否则执行7。同理从最高点向右遍历更新ans。

向左找的具体操作

将每一个点的高度和索引存成一个元组 (val, idx)将元组按val从大到小排序，若val相等，按idx从大到小排序。实现过程：直接sort，然后reverse。从左向右遍历，找到第一个idx小于now_idx的节点(left_val, left_idx)，用height[left+1, now-1]中的点更新ans。更新now节点为left节点。如果now_idx >= 0 ，重复执行3；否则结束循环，开始向右找。

向右找的具体操作

将每一个点的高度和索引存成一个元组 (val, idx)将元组按val从大到小排序，若val相等，按idx从小到大排序。实现过程：用functools中的cmp_to_key重载排序过程。从左向右遍历，找到第一个idx大于now_idx的节点(right_val, right_idx)，用height[now+1, right-1]中的点更新ans。更新now节点为lright节点。如果now_idx >= 0 ，重复执行3；否则执行6。输出ans。

注意：向左向右只有排序不同，其他操作类似，

利用functools中的cmp_to_key重载排序过程代码如下：

def mcmp(a, b): val1,idx1 = a val2,idx2 = b if val1 == val2: return idx2-idx1 return val1-val2 from functools import cmp_to_key l = [] # l中存元组(val, idx) l.sort(reverse=True, key=cmp_to_key(Solution.mcmp))

代码如下

class Solution: # 利用functools中的cmp_to_key重载排序： def mcmp(a, b): val1,idx1 = a val2,idx2 = b if val1 == val2: return idx2-idx1 return val1-val2 def trap(self, height: List[int]) -> int: if len(height) == 0: return 0 from functools import cmp_to_key l = [] # 将(val, idx)存入l = []中 for i in range(0, len(height)): l.append((height[i],i)) ans = 0 # 往左找 l.sort(reverse=True) h, con = l[0] for i in range(1, len(l)): val, left = l[i] if left < con: for j in range(left+1, con): ans += val - height[j] con = left # 往右找 h, con = l[0] l.sort(reverse=True, key=cmp_to_key(Solution.mcmp)) for i in range(1, len(l)): val, right = l[i] if right > con: for j in range(con+1, right): ans += val - height[j] con = right return ans

C++解法

解题思路：

本思路与Python类似，需找到最高点左右遍历，时间复杂度O（nlogn）以下为向左遍历的过程。差别在于C++是存map，无须手动排序。

// m中first存高度val，second存索引集合。 // set<int> s = m[2]表示高度为2的点的位置集合。 map<int, set<int>> m;

实现代码如下：

class Solution { public: int trap(vector<int>& height) { if(height.size() == 0) return 0; int ans = 0; // m中first存高度val，second存索引集合。 // set<int> s = m[2]表示高度为2的点的位置集合。 map<int, set<int>> m; // itm表示m的一个迭代器 map<int, set<int>>::iterator itm; set<int> s; set<int>::iterator its; //将(val, idx)存入map int sz = height.size(); for(int i = 0;i < sz; ++i){ m[height[i]].insert(i); } //向左找 itm = --m.end(); s = itm->second; int h = itm->first; int left = *s.begin(); //每次找val小，idx小的 while(left != -1 && left >= 0){ s = m[h]; its = s.lower_bound(left); if(its == s.begin()){ if(itm == m.begin()){ left = -1; }else{ --itm; h = itm->first; } }else{ --its; for(int i = *its+1;i < left; ++i){ ans += h-height[i]; } left = *its; continue; } } //向右找 itm = --m.end(); s = itm->second; h = itm->first; int right = *s.begin(); //每次找val小，idx大的 while(right != -1 && right < sz){ s = m[h]; its = s.upper_bound(right); if(its == s.end()){ if(itm == m.begin()){ right = -1; }else{ --itm; h = itm->first; } }else{ for(int i = right+1;i < *its; ++i){ ans += h-height[i]; } right = *its; continue; } } return ans; } };