LeetCode 42. Trapping Rain Water

Python解法

解題思路：

本思路需找到最高點(diǎn)左右遍歷，時間復(fù)雜度O（nlogn），以下為向左遍歷的過程。

將每一個點(diǎn)的高度和索引存成一個元組 (val, idx)

找到最高的點(diǎn)（可能有多個，任取一個），記為 (now_val, now_idx)。

向左找第一個val不大于now_val的點(diǎn)(left_val, left_idx)。

以left_val作為水平面，用height[left_val+1, now_val-1]中每一個點(diǎn)更新ans。

now_val, now_idx = left_val, left_idx。

如果now_idx >= 0 ，重復(fù)執(zhí)行3；否則執(zhí)行7。

同理從最高點(diǎn)向右遍歷更新ans。

向左找的具體操作

將每一個點(diǎn)的高度和索引存成一個元組 (val, idx)

將元組按val從大到小排序，若val相等，按idx從大到小排序。實現(xiàn)過程：直接sort，然后reverse。

從左向右遍歷，找到第一個idx小于now_idx的節(jié)點(diǎn)(left_val, left_idx)，用height[left+1, now-1]中的點(diǎn)更新ans。

更新now節(jié)點(diǎn)為left節(jié)點(diǎn)。

如果now_idx >= 0 ，重復(fù)執(zhí)行3；否則結(jié)束循環(huán)，開始向右找。

向右找的具體操作

將每一個點(diǎn)的高度和索引存成一個元組 (val, idx)

將元組按val從大到小排序，若val相等，按idx從小到大排序。實現(xiàn)過程：用functools中的cmp_to_key重載排序過程。

從左向右遍歷，找到第一個idx大于now_idx的節(jié)點(diǎn)(right_val, right_idx)，用height[now+1, right-1]中的點(diǎn)更新ans。

更新now節(jié)點(diǎn)為lright節(jié)點(diǎn)。

如果now_idx >= 0 ，重復(fù)執(zhí)行3；否則執(zhí)行6。

輸出ans。

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

利用functools中的cmp_to_key重載排序過程代碼如下：

def mcmp(a, b):val1,idx1 = aval2,idx2 = bif val1 == val2:return idx2-idx1return val1-val2from 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 = aval2,idx2 = bif val1 == val2:return idx2-idx1return val1-val2def trap(self, height: List[int]) -> int:if len(height) == 0:return 0from functools import cmp_to_keyl = []# 將(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 = rightreturn ans

C++解法

解題思路：

本思路與Python類似，需找到最高點(diǎn)左右遍歷，時間復(fù)雜度O（nlogn）以下為向左遍歷的過程。差別在于C++是存map，無須手動排序。

// m中first存高度val，second存索引集合。 // set<int> s = m[2]表示高度為2的點(diǎn)的位置集合。 map<int, set<int>> m;

實現(xiàn)代碼如下：

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的點(diǎn)的位置集合。map<int, set<int>> m;// itm表示m的一個迭代器map<int, set<int>>::iterator itm;set<int> s;set<int>::iterator its;//將(val, idx)存入mapint 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;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 42. Trapping Rain Water 【两种解法】（python排序遍历，C++ STL map存索引，时间复杂度O（nlogn））的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。