Leetcode 503: Следующий великий элемент II

Руководство по решению общей инвестиционной проблемы

В этой статье мы обсудим проблему, когда у нас есть определенный начальный капитал, и мы хотим инвестировать его в проекты, чтобы максимизировать нашу прибыль. У каждого проекта есть прибыль и потребность в капитале, и мы можем инвестировать только в ограниченное количество проектов.

Ссылка на вопрос: https://leetcode.com/problems/next-greater-element-ii/description/

Постановка задачи

Нам дано целое число k, представляющее максимальное количество проектов, в которые мы можем инвестировать, целое число w, представляющее наш начальный капитал, два массива целых чисел profits и capital, представляющие прибыль и потребность в капитале для каждого проекта. Нам нужно найти максимальный капитал, который мы можем иметь после инвестирования не более чем в k проектов.

Подход

Мы можем начать с создания массива проектов, отсортированных по их потребности в капитале. Затем мы можем создать максимальную кучу для хранения доступной прибыли. Мы будем перебирать проекты и добавлять все доступные проекты в максимальную кучу, пока не достигнем максимального количества проектов, в которые мы можем инвестировать, или у нас не закончатся доступные проекты. Мы выберем проект с наибольшей прибылью из кучи и удалим его из кучи. Мы будем повторять этот процесс до тех пор, пока не инвестируем не более k проектов или пока у нас не закончатся доступные проекты.

Код

Вот код JavaScript для решения проблемы:

function findMaximizedCapital(k, w, profits, capital) {
  // Create an array of projects, sorted by their capital requirement
  const projects = [];
  for (let i = 0; i < profits.length; i++) {
    projects.push([capital[i], profits[i]]);
  }
  projects.sort((a, b) => a[0] - b[0]);
  // Create a max heap to store available profits
  const maxHeap = new MaxHeap();
  let i = 0;
  while (k > 0) {
    // Add all available projects to the max heap
    while (i < projects.length && projects[i][0] <= w) {
      maxHeap.insert(projects[i][1]);
      i++;
    }
    // If there are no available projects, return the current capital
    if (maxHeap.isEmpty()) {
      return w;
    }
    // Choose the project with the highest profit and remove it from the heap
    w += maxHeap.extractMax();
    k--;
  }
  return w;
}
class MaxHeap {
  constructor() {
    this.heap = [];
  }
  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }
  extractMax() {
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown(0);
    }
    return max;
  }
  isEmpty() {
    return this.heap.length === 0;
  }
  bubbleUp(index) {
    const value = this.heap[index];
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parent = this.heap[parentIndex];
      if (value <= parent) {
        break;
      }
      this.heap[parentIndex] = value;
      this.heap[index] = parent;
      index = parentIndex;
    }
  }
  sinkDown(index) {
    const value = this.heap[index];
    const length = this.heap.length;
    while (true) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;
      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild > value) {
          swap = leftChildIndex;
        }
      }
      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if (
          (swap === null && rightChild > value) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIndex;
        }
      }
      if (swap === null) {
        break;
      }
      this.heap[index] = this.heap[swap];
      this.heap[swap] = value;
      index = swap;
    }
  }
}

Пример

Вот пример использования функции findMaximizedCapital:

const k = 2;
const w = 0;
const profits = [1, 2, 3];
const capital = [0, 1, 1];
console.log(findMaximizedCapital(k, w, profits, capital)); // Output: 4

В этом примере у нас есть начальный капитал 0, и мы можем инвестировать не более 2 проектов. У нас есть три доступных проекта, каждый с прибылью и капиталом. Мы можем инвестировать в первый и второй проекты, которые имеют общую прибыль 1 + 2 = 3 и общую потребность в капитале 0 + 1 = 1. Наш окончательный капитал будет равен 0 + 3 = 3, но мы можем инвестировать не более чем в 2 проектов, поэтому мы инвестируем в первый и третий проекты, общая прибыль которых составляет 1 + 3 = 4, а общая потребность в капитале составляет 0 + 1 = 1. Наша последняя столица 0 + 4 = 4.

Заключение

В этой статье мы обсудили проблему, когда у нас есть определенный начальный капитал, и мы хотим инвестировать его в проекты, чтобы максимизировать нашу прибыль. Мы показали подход к решению проблемы с использованием максимальной кучи и предоставили реализацию на JavaScript.