31. Next Permutation.txt

//Моё решение. Блять решал 6 часов вот я тупой. Но получилось.
//Проходим по всему массиву начиная с конца. Первый элемент у нас будет nums.size() - 2.
//Если элемент справа от нас [i + 1] больше нашего iого элемента, то просто меняем их местами и завершаем функцию.
//Если элемент слева [i - 1] меньше нашего iого элемента, то сортируем по возрастанию все элементы, начиная с i(включительно).
//	Далее ищем первый элемент, который больше [i - 1], и меняем их местами. Завершаем функцию.
//Если весь массив пройден, но ни одно из условий не выполнелось, значит перестановка в массиве является последней. Нам нужно просто инвертировать массив и всё.
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        for (int i = nums.size() - 2; i > 0; i--) {
            if (nums[i] < nums[i + 1]) {
                swap(nums[i], nums[i + 1]);
                return;
            }
            if (nums[i] > nums[i - 1]) {
                int j = i;
                sort(nums.begin() + i, nums.end());
                while (nums[i - 1] >= nums[j])
                    j++;
                swap(nums[i - 1], nums[j]);
                return;
            }
        }
        reverse(nums.begin(), nums.end());
    }
};



//Самое быстрое решение на leetcode
//Суть таже просто у него нет вложенного цикла как у меня, по этому быстрее.
//Только он сначала ищет число большее и переставляет его, а уже потом делает сортировку.
class Solution {
public:
    void nextPermutation(vector<int>& nums) {//peakdown==breakingpoint;
        int n = nums.size();  
        int peakdownn = -1;
        for (int i = n - 2; i >=0; i--) {
            if (nums[i] < nums[i + 1]) {
                peakdownn = i;
                break; 
            }
        }
        if (peakdownn==-1) {
            reverse(nums.begin(), nums.end());
        }
        
        else{
        for (int i = n - 1; i > peakdownn; i--) {
            if (nums[i] > nums[peakdownn]) {
                swap(nums[i], nums[peakdownn]);
                break;
            }
          
        }
          reverse(nums.begin() + peakdownn + 1, nums.end());
       }

       
    }
};