GE Vernova

01The Best Subsequence || Find the minimum of special value of a subsequence

You are given an array arr of size n and an integer k. A subsequence is defined as a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. You need to find a subsequence of size k and calculate its special value. The special value of a subsequence of size k is defined as: Summation of absolute difference of consecutive numbers. For i = 2 to k, abs(pi - p(i-1)). Your task is to find the minimum possible special value among all subsequences of size k in the array.

Example 1

Input:

arr = [9, 5, 1, 4, 9]
k = 2

Output:

Explanation: Subsequence : {9, 9}

Example 2

Input:

arr = [9, 5, 1, 4, 9, 100]
k = 3

Output:

Explanation: Subsequence : {9, 5, 4}

解法

先排序：若排序后 a 中取相邻 k 个元素，相邻差之和 = a[i+k-1] - a[i](因为中间项 telescopes)。由于在原数组里子序列保持原顺序，但 |·| 对调换顺序不变，所以最优子序列在排序后必然是连续 k 个。扫描排序后所有长度为 k 的窗口取最小 a[i+k-1]-a[i]。时间 O(n log n)，空间 O(1)。

from typing import List

def find_minimum_special_value(arr: List[int], k: int) -> int:
    if k <= 1:
        return 0
    a = sorted(arr)
    return min(a[i + k - 1] - a[i] for i in range(len(a) - k + 1))

import java.util.*;

class Solution {
    public int findMinimumSpecialValue(int[] arr, int k) {
        if (k <= 1) return 0;
        int[] a = arr.clone();
        Arrays.sort(a);
        int best = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < a.length; i++) {
            best = Math.min(best, a[i + k - 1] - a[i]);
        }
        return best;
    }
}

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

class Solution {
public:
    int findMinimumSpecialValue(vector<int>& arr, int k) {
        if (k <= 1) return 0;
        vector<int> a = arr;
        sort(a.begin(), a.end());
        int best = INT_MAX;
        for (int i = 0; i + k - 1 < (int)a.size(); i++) {
            best = min(best, a[i + k - 1] - a[i]);
        }
        return best;
    }
};