Вопрос:

Ссылка: https://leetcode.com/problems/maximum-subsequence-score/description/

Вам даны два индексированных 0 целочисленных массива nums1 и nums2 одинаковой длины n и положительного целого числа k. Вы должны выбрать подпоследовательность индексов из nums1 длины k.

Для выбранных индексов i0, i1, ..., ik - 1 ваша оценка определяется как:

  • Сумма выбранных элементов из nums1, умноженная на минимум выбранных элементов из nums2.
  • Его можно определить просто как: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).

Возвратите максимальный возможный балл.

Подпоследовательность индексов массива — это набор, который может быть получен из набора {0, 1, ..., n-1} путем удаления некоторых элементов или их отсутствия.

Пример 1:

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation: 
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. 
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. 
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.

Пример 2:

Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
Output: 30
Explanation: 
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

Ограничения:

  • n == nums1.length == nums2.length
  • 1 <= n <= 105
  • 0 <= nums1[i], nums2[j] <= 105
  • 1 <= k <= n

Решение:

Подход:

  1. Метод maxScore принимает три входных параметра: nums1 и nums2 (два массива) и k (количество элементов для выбора).
  2. Код инициализирует переменную n длиной nums1, предполагая, что nums1 и nums2 имеют одинаковую длину.
  3. Код создает двумерный массив pairs размером n на 2 для хранения пар элементов из nums1 и nums2. Каждая пара представлена ​​в виде массива с двумя элементами: значением из nums1 и соответствующим значением из nums2.
  4. Массив pairs сортируется по второму элементу каждой пары в порядке убывания. Этот шаг сортировки гарантирует, что элементы с более высокими значениями в nums2 рассматриваются в первую очередь при выборе.
  5. Очередь с приоритетом heap создается с размером k и пользовательским компаратором, который упорядочивает элементы в порядке возрастания.
  6. Код инициализирует переменную ksum для отслеживания суммы выбранных элементов из nums1. Он начинается с суммирования первых k элементов из nums1 и добавления их к ksum. Кроме того, эти элементы добавляются в файл heap.
  7. Переменная ans инициализируется произведением ksum и второго элемента последней пары в массиве pairs (поскольку массив сортируется в порядке убывания на основе второго элемента).
  8. Код перебирает оставшиеся пары, начиная с индекса k до n-1.
  9. Для каждой пары он вычитает элемент с индексом i-k (элемент, который был добавлен k итераций назад) из ksum и добавляет текущий элемент к ksum. Это эффективно обновляет сумму выбранных элементов из nums1 по мере перемещения скользящего окна.
  10. Элемент с индексом i-k удаляется из heap, а текущий элемент добавляется к heap.
  11. Код вычисляет произведение ksum и второго элемента текущей пары и обновляет ans, если это произведение больше текущего ans. Этот шаг находит максимально возможное количество очков.
  12. Наконец, возвращается максимальный балл ans.
class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int[][] pairs = new int[n][2];

        for(int i=0; i<n; i++){
            pairs[i] = new int[]{nums1[i], nums2[i]};
        }

        Arrays.sort(pairs, (a,b)->b[1] - a[1]);

        PriorityQueue<Integer> heap = new PriorityQueue<>(k, (a,b)->a-b);
        long ksum = 0;
        for(int i=0; i<k; i++){
            ksum += pairs[i][0];
            heap.add(pairs[i][0]);
        }

        long ans = ksum * pairs[k-1][1];

        for(int i=k; i<n; i++){
            ksum += pairs[i][0] - heap.poll();
            heap.add(pairs[i][0]);

            ans = Math.max(ans, ksum * pairs[i][1]);
        }
        return ans;
    }
}

Временная сложность: O(N logN)

Космическая сложность: O(K)

Заключение:

Надеюсь, что этот блог поможет вам решить вопрос, а также развеет ваши сомнения относительно решения. Пожалуйста, прокомментируйте, если вы знаете какие-либо новые подходы. Если у вас есть какие-либо сомнения, пожалуйста, прокомментируйте, и мы обсудим их.

Удачного кодирования.