動機

每次看經典題與他的解答都是新的發現

這邊居然有dp 與 two pointer

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]Output: 9

 

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

Sol

一個會看到只要後面有更高的就可以把前面比較矮的給忽略掉，所以可以用stack存高到矮的牆，等高的出現，就可以一直pop算每一層的水

class Solution:
    def trap(self, hs: List[int]) -> int:
        stk = [] #premise: hs[stk[0]] > hs[stk[any i which is > 0]]
        ret = 0
        for i in range(len(hs)):
            if stk:
                if hs[stk[-1]] < hs[i]:
                    base_height = hs[stk.pop()] # pop bottom
                    while stk and hs[stk[-1]] <= hs[i]:
                        ret += (i-stk[-1]-1)*(min(hs[stk[-1]],hs[i])-base_height)
                        base_height = hs[stk.pop()]
                    if stk:
                        ret += (i-stk[-1]-1)*(min(hs[stk[-1]],hs[i])-base_height)
                elif hs[stk[-1]] == hs[i]:
                    stk.pop()
            stk.append(i)
            #print(i,stk,ret)
        return ret

或者是看成柱子一路長高的過程，再走的時候記下柱子與目前最高的差距

class Solution:
    def trap(self, hs: List[int]) -> int:
        a,b,ret = 0,len(hs)-1,0
        leftH, rightH = 0,0
        while a < b:
            if hs[a] < hs[b]:
                if hs[a] >= leftH:
                    leftH = hs[a]
                else:
                    ret += leftH-hs[a]
                a += 1
            else:
                if hs[b] >= rightH:
                    rightH = hs[b]
                else:
                    ret += rightH-hs[b]
                b -= 1
        return ret

但也不用兩邊都算，因為我們只要取最小的就好，所以只要累計左右最小的那一邊就好，如此一來就可以兩邊輪流算!! 就變成two pointer

class Solution:
    def trap(self, hs: List[int]) -> int:
        a,b,ret = 0,len(hs)-1,0
        leftH, rightH = 0,0
        while a < b:
            if hs[a] < hs[b]:
                if hs[a] >= leftH:
                    leftH = hs[a]
                else:
                    ret += leftH-hs[a]
                a += 1
            else:
                if hs[b] >= rightH:
                    rightH = hs[b]
                else:
                    ret += rightH-hs[b]
                b -= 1
        return ret