[LeetCode] Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

 int solution(vector<int>& height) {
     int answer = 0;
     int maxHeightIndex = max_element(height.begin(), height.end())-height.begin();
     int maxHeight = 0;
     for (int i = 0; i < maxHeightIndex; i++)
     {
         if (maxHeight <= height[i]) maxHeight = height[i];
         else
         {
             answer += maxHeight - height[i];
         }
     }
     maxHeight = 0;
     for (int i = height.size() - 1; i > maxHeightIndex; i--)
     {
         if (maxHeight <= height[i]) maxHeight = height[i];
         else
         {
             answer += maxHeight - height[i];
         }
     }
     return answer;
}

풀이

최고점을 먼저 찾는다 -> 점점 최고점으로 양쪽에서 다가가도록 for문을 두번 돌린다. -> i보다 maxHeight가 작다면 i를 maxHeight에 저장하고 ///  i보다 maxHeight가 크다면 maxHeight-height[i]만큼 answer에 더해준다. (이게 가능한 이유는 최고점으로 다가가서,  maxHeight-height[i]이 아닌 더 적은 물이 채워질 가능성을 배제했기 때문이다.)