[LeetCode] 42. Trapping Rain Water

• Problem: Trapping Rain Water, 利用 histogram 的圖形, 統計可以接的雨水量
• Concept:
• 第 i 個 bin 能接的水量, 被左右高度所決定 (取其小的)
• 而左右的高度, 相當於持續統計的結果 

• leftMaxHeight (i) = max { leftMaxHeight[i-1], height [i-1] }

• 同理, rightMaxHeight 也是, 只是要由右往左統計
• Implementation:

• class Solution {
  public:
      int trap(vector& height) {
          int result = 0;
          if (height.size() < 2) return result;
          vector leftMaxHeight;
          vector rightMaxHeight(height.size(), 0);
          
          leftMaxHeight.push_back(0);
          for (int i = 1; i < height.size(); i++) {                
              leftMaxHeight.push_back(max(leftMaxHeight[i-1], height[i-1]));
          }
          
          for (int i = height.size() - 2; i >= 0; i--) {
              rightMaxHeight[i] = max(rightMaxHeight[i+1], height[i+1]);
          }
          
          for (int i = 0; i < height.size(); i++) {
              int h = min (leftMaxHeight[i], rightMaxHeight[i]) - height[i];
              if (h > 0) result += h;
          }
          return result;
      }
  };
  

[Programming] Recursive

• Programming problems 中重要的一個分類就是 recursive
• e.g. 著名的 n 階算法
int factorial(int n) { if (1 == n) return 1; if (0 == n) return 1; return n * factorial(n-1); }
• 但更重要的是應該要考慮 recursive 的限制
• stack overflow
• 解法: 
• tail recursive
• 連結內的解釋相當清楚, 主要是透過寫法不同, 讓 compiler 在 O2, O3的 optimization時, 不用 call function, 而是 jne (jump not equal)

• int factorial_acc(int n, int acc = 1) 
  {    
      if (n == 1) 
          return acc;
      else
          return factorial_acc(n - 1, n * acc);
  }
  

• iterative

• int factorial_iterative(int n)
  {
      int acc = 1;
      if (n <= 1) return acc;
      while (n > 1)
      {
          acc *= n;
          n--;
      }
      return sum;
  }

• 延伸閱讀
• Iterative vs. Recursive
• Stack size
• stack vs heap