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)); // 输出：4

这个例子中，我们有一个初始资本0，我们可以投资最多的2项目。我们有三个可用项目，每个项目都有利润和资本要求。我们可以投资第一个和第二个项目，它们的总利润为1 + 2 = 3，总资本需求为0 + 1 = 1。我们的最终资本为0 + 3 = 3，但我们最多只能投资于大多数2项目，因此我们投资于第一和第三个项目，这两个项目的总利润为1 + 3 = 4，总资本需求为0 + 1 = 1。我们的最终资本是0 + 4 = 4。

结论

在本文中，我们讨论了一个问题，即我们拥有一定数量的初始资金，我们希望将其投资于项目以实现利润最大化。我们已经展示了一种使用最大堆解决问题的方法，并且我们提供了一个 JavaScript 实现。