42. Trapping Rain Water.txt

//Два оптимальных кода. (Какой лучше хз) Вопрос на будующее. Немного подумав обнаружил что принцып то одинаковый у обоих решений.
//Бля как я сразу не додумался. Не нужно в ответ складывать сразу все ячейки с водой.
//Этот код работает так: ОБе границы сближаются с друг другом только ОДИН раз. Граница, значение которой МЕНЬШЕ производит движение.
//Если левая граница меньше или равна правой границе по значению то двигается левая. Если наоборот правая граница меньше, то она и двигается.
//По ходу движения границ, мы записываем максимальные значения этих границ. Если текущее значение меньше максимального, значит мы ушли вниз, и нужно записывать результат.
//Результат записывается поэтапно, с каждым ходом, а не весь сразу, как у меня. Результат = максимальное значение границы минус текущее значение.
class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0; int right = height.size() - 1;//Объявляем границы
        int res = 0;//Вывод результата
        int maxleft = 0, maxright = 0;//Максимальные значения границ
        while (left <= right) {//Цикл пока левая граница не встретится с правой
            if (height[left] <= height[right]) {//Если значение левой границы меньше или = значению правой границы
                if (height[left] >= maxleft) maxleft = height[left];//Если значение левой границы больше или = предыдущему максимальному значению, сохраняем новое значение
                else res += maxleft - height[left];//Иначе результат равен результату + максимальному значению левой границы минус текущее значение левой границы
                left++;//Смещаем левую границу на + 1
            }
            else {//Если значение левой границы больше значения правой границы
                if (height[right] >= maxright) maxright = height[right];//Если значение правой границы больше или = предыдущему максимальному значению, сохраняем новое значение
                else res += maxright - height[right];//Иначе результат равен результату + максимальному значению правой границы минус текущее значение правой границы
                right--;//Смещаем правую границу на - 1
            }
        }
        return res;//Вохвращаем результат
    }
};


//Это решение вообще разъёб. Не знаю эффективнее предыдущего или нет, но очень крутое.
//Обе границы проходят значения вектора height с разных сторон. Левый вектор - слева направо, правый - справа налево.
//При этом каждая граница записывает в свой вектор максимальное значение между предыдущим своим значением и текущим значением вектора height. Максимальное значение не становится меньше.
//Пример: height = {0,1,2,3,2,1,0}. Вектор left будет равен: left{0,1,2,3,3,3,3}. Вектор right будет равен: right{3,3,3,3,2,1,0}.
//Для получения результата мы заново проходим вектор height. 
//Ответ будет равен минимальному значению между iым элементом векторов left и right минус iым значение вектора height.
height = {0,1,0,2,1,0,1,3,2,1,2,0,1}  0,1,0,2,1,0,1,3,2,1,2,0,1                                                                 
left =   {0,1,1,2,2,2,2,3,3,3,3,3,3}  0,1,1,2,2,2,2,3,                                                                          
right =  {3,3,3,3,3,3,3,3,2,2,2,1,1}                3,2,2,2,1,1                                                                           
				ans = 0,0,1,0,1,2,1,0,0,1,0,1,0
//Гениально!

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        vector<int> left(n);
        vector<int> right(n);
        left[0]=height[0];
        for(int i=1;i<n;i++){
            left[i]=max(left[i-1],height[i]);
        }

        right[n-1]=height[n-1];
        for(int i=n-2;i>=0;i--){
            right[i]=max(right[i+1],height[i]);
        }

        int ans=0;
        for(int i=0;i<n;i++){
            ans+=min(left[i],right[i])-height[i];
        }

        return ans;
    }
};



//Мой код.//Проходим весь вектор левой границей, правой границей ищем вторую стенку.
//Если близжайший пик = -1, а левый и наивысший стоят вплотную рядом, то прибавляем левыой границе + 1 и пробуем ещё раз.
//Если близжайший пик = -1, наивысший и левый не стоят рядом, вычисляем кол-во воды между ними.
//В остальных случаях вычисляем между левым и близжайшим пиком.

class Solution {
public:
    int answerPush(int left, int right, int answer, vector<int>& height) {
        int bottom = 0;
        int tempRight = right;
        while (left != tempRight) {
            bottom += height[tempRight];
            tempRight--;
        }
        bottom -= height[right];

        int waterLevel = min(height[left], height[right]);
        int distance =  right - left - 1;
        answer += (distance * waterLevel - bottom);
        return answer;
    }
    int trap(vector<int>& height) {
        int answer = 0;
        int leftIndex = 0;
        while (leftIndex < height.size() - 1) {
            while (leftIndex != height.size() - 1 && height[leftIndex + 1] >= height[leftIndex]) {
                leftIndex++;
            }
            int rightIndex = height.size() - 1;
            //Ищем близжайший и наивысший пик
            int nearPeak = -1, highestPeak = rightIndex;
            while (rightIndex != leftIndex) {
                if (height[rightIndex] >= height[highestPeak])
                    highestPeak = rightIndex;
                if (height[rightIndex] >= height[leftIndex])
                    nearPeak = rightIndex;
                rightIndex--;
            }
            if (highestPeak - leftIndex == 1) {
                    leftIndex++;//И ещё раз
            }
            else if (nearPeak == -1) {
                answer = answerPush(leftIndex, highestPeak, answer, height);
                leftIndex = highestPeak;
            }
            else{
                answer = answerPush(leftIndex, nearPeak, answer, height);
                leftIndex = nearPeak;
            }	
        }
        return answer;
    }
};
};