1053. Previous Permutation With One Swap

leetcode medium

#array#csharp#graph#leetcode#medium#sliding-window

Task

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

Input: arr = [3,2,1]

Output: [3,1,2]

C# solution

matched/original

public class Solution {
    public int[] PrevPermOpt1(int[] arr) {
        int n = arr.Length;
        int i;
        for (i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                break;
            }
        }
        if (i == -1) {
            return arr;
        }
        
        int j;
        for (j = n - 1; j > i; j--) {
            if (arr[j] < arr[i] && (j == n - 1 || arr[j] != arr[j + 1])) {
                break;
            }
        }
        
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        return arr;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& PrevPermOpt1(vector<int>& arr) {
        int n = arr.size();
        int i;
        for (i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                break;
            }
        }
        if (i == -1) {
            return arr;
        }
        
        int j;
        for (j = n - 1; j > i; j--) {
            if (arr[j] < arr[i] && (j == n - 1 || arr[j] != arr[j + 1])) {
                break;
            }
        }
        
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        return arr;
    }
}

Java solution

matched/original

public class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        int i;
        for (i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                break;
            }
        }
        if (i == -1) {
            return arr;
        }
        
        int j;
        for (j = n - 1; j > i; j--) {
            if (arr[j] < arr[i] && (j == n - 1 || arr[j] != arr[j + 1])) {
                break;
            }
        }
        
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        return arr;
    }
}

JavaScript solution

matched/original

function prevPermOpt1(arr) {
    const n = arr.length;
    let i;
    for (i = n - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1]) {
            break;
        }
    }
    if (i === -1) {
        return arr;
    }
    
    let j;
    for (j = n - 1; j > i; j--) {
        if (arr[j] < arr[i] && (j === n - 1 || arr[j] !== arr[j + 1])) {
            break;
        }
    }
    
    [arr[i], arr[j]] = [arr[j], arr[i]];
    
    return arr;
}

Python solution

matched/original

def prevPermOpt1(arr):
    n = len(arr)
    for i in range(n - 2, -1, -1):
        if arr[i] > arr[i + 1]:
            break
    else:
        return arr
    
    for j in range(n - 1, i, -1):
        if arr[j] < arr[i] and (j == n - 1 or arr[j] != arr[j + 1]):
            break
    
    arr[i], arr[j] = arr[j], arr[i]
    
    return arr

Go solution

matched/original

package main

func prevPermOpt1(arr []int) []int {
    n := len(arr)
    var i int
    for i = n - 2; i >= 0; i-- {
        if arr[i] > arr[i+1] {
            break
        }
    }
    if i == -1 {
        return arr
    }

    var j int
    for j = n - 1; j > i; j-- {
        if arr[j] < arr[i] && (j == n-1 || arr[j] != arr[j+1]) {
            break
        }
    }

    arr[i], arr[j] = arr[j], arr[i]
    
    return arr
}

func main() {
    arr := []int{3, 2, 1}
    result := prevPermOpt1(arr)
    fmt.Println(result)
}

Explanation

Algorithm

Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

Пройди по массиву, используя скользящее окно для учета эффекта от техники.

Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.

😎