Ruby Solution


  • 0
    I

    Three parts

    1. My plain solution
    2. Two pointers scanning by Sharing my simple c++ code: O(n) time, O(1) space
    3. Stack based solution by A stack based solution for reference, inspired by Histogram

    The basic idea is: Find the valley, check the lower boundary (peak), and fill water.


    My plain solution

      # Solution - plain
      def trap(height)
        return 0 if height.length == 0
    
        # make head and tail of height are peaks
        pre_process!(height)
    
        # find max element's index
        max_ele, max_idx = -1, -1
    
        height.each_with_index do |ele, idx|
          next if max_ele >= ele
    
          max_ele = ele
          max_idx = idx
        end
    
        calc_trap(height[0..max_idx]) + calc_trap(height[max_idx..-1].reverse)
      end
    
      # Pre-condition: tail of height is the max element
      def calc_trap(height)
        return 0 if height.length < 3
    
        n = height.length
        pos = 0
        res = 0
        peak = height[0]
    
        loop do
          p1 = pos
          pos += 1 while pos+1 < n && height[pos] >= height[pos+1]
          pos += 1 while pos+1 < n && height[pos] <= height[pos+1]
          p2 = pos
    
          height[p1+1..p2].each do |ele|
            next if peak <= ele
            res += (peak - ele)
          end
    
          peak = height[pos] if peak < height[pos]
    
          # puts "height: #{height}"
          # puts "p1: #{p1} p2: #{p2}"
          # puts "h1: #{height[p1]} h2: #{height[p2]}"
          # puts "peak: #{peak}, res: #{res}"
    
          break if pos+1 == n
        end
    
        res
      end
    
      def pre_process!(height)
        n = height.length
    
        # shift until the first peak
        i = 0
        i += 1 while i+1 < n && height[i] <= height[i+1]
    
        # pop until the last peak
        j = n-1
        j -= 1 while j-1 >= 0 && height[j] <= height[j-1]
    
        return 0 if i >= j
    
        height[i..j]
      end
    

    Two pointers scanning by Sharing my simple c++ code: O(n) time, O(1) space

      # Solution - two pointers
      def trap(height)
        left_max, right_max = 0, 0
        head, tail = 0, height.length-1
        water = 0
    
        while head <= tail
          left, right = height.values_at(head, tail)
    
          if left <= right
            left_max < left ? left_max = left : (water += left_max - left)
            head += 1
          else
            right_max < right ? right_max = right : (water += right_max - right)
            tail -= 1
          end
        end
    
        water
      end
    d
    
    

    Stack based solution by A stack based solution for reference, inspired by Histogram

      # Solution - stack
      def trap(height)
        water = 0
        stack = [] # used to store the index of height
        i = 0
    
        while i < height.length
          if stack.empty? or height[i] <= height[ stack.last ]
            stack << i
            i += 1
          else
            valley = height[ stack.pop ]
    
            next if stack.empty?
    
            left_idx, right_idx = stack.last, i
            peak = height.values_at(left_idx, right_idx).min
    
            water += (peak - valley) * (right_idx - left_idx - 1)
          end
        end
    
        water
      end
    

Log in to reply
 

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