Python Recursive O(n) time O(n) space with Stack


  • 0
    N

    The idea is actually similar to the O(1) space solution, but not as intuitive.

    class Solution(object):
        def trap(self, height):
            if len(height) <= 2:
                return 0
            i = 0
            lo = 0
            total = 0
            stk = []
            while i < len(height):
                if height[i] != 0:
                    lo = height[i]
                    stk = [lo]
                    j = i + 1
                    while j < len(height) and height[j] < height[i]:
                        stk.append(height[j])
                        j += 1
                    if j < len(height):
                        while stk:
                            total += (lo - stk.pop())
                    i = j - 1
                i += 1
            if stk:
                total += self.trap(stk[::-1])
            return total
    

Log in to reply
 

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