502.ipo.md

我们只有 W 的资本，可以做 K 个项目，那么我们肯定要优先选择我们能做的可以获取最大收益的前 K 个项目，很显然这是一个贪心问题

问题是，怎么确定我们能做的 K 个项目呢？

我们想到了优先队列，这个优先队列存储的是每个项目的收益和成本，compare 条件很显然应该是收益大，成本小优先

我们按这个原则出堆的时候，堆顶的项目存在两种情况：

• 项目启动资金大于我们当前资本：
  • 堆顶的项目虽然收益可能最大，但是受制于项目启动资金，项目不能做，于是我们要继续寻找能产生次大收益的项目；
  • 这些出堆的项目我们暂时保存在一个缓冲区，等待我们做了一个可以做的项目，这时候我们的资本就增加了，可以把缓冲区的项目重新入堆
• 项目启动资金小于等于我们当前资本：
  • 项目可以做

代码实现：

class Node {
    int p, c;

    public Node(int p, int c) {
        this.p = p;
        this.c = c;
    }
}

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        PriorityQueue<Node> heap = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.p == o2.p) {
                    return o1.c - o2.c; // 小顶
                }
                return o2.p - o1.p; // 大顶
            }
        });

        for (int i = 0; i < n; i++) {
            heap.add(new Node(profits[i], capital[i]));
        }
        while (k-- > 0) {
            List<Node> buf = new ArrayList<>();
            while (!heap.isEmpty()) {
                Node top = heap.poll();
                if (top.c > w) {
                    buf.add(top);
                } else {
                    w += top.p;
                    heap.addAll(buf);
                    if(!buf.isEmpty()) buf.clear();
                    break;
                }
            }
            if (!buf.isEmpty()) return w; // 没有可以做的项目了
        }

        return w;
    }

}

提交后，我们发现上面的代码执行效率比较低，如何优化一下呢？

我们有必要一开始把所有数据都入堆吗，想一下，实际场景中，我们只需要关心我们可以做的项目，不能做的项目我们没必要入堆，我们不能每次都遍历所有项目吧，这样效率会很低，于是我们考虑把按照项目的启动资金从小到大排序，并使用一个游标记录遍历到的成本最小项目索引，优化后的代码如下：

class Solution {

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        // 按纯利从大到小
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int[][] project = new int[n][2];
        for (int i = 0; i < n; i++) {
            project[i][0] = profits[i];
            project[i][1] = capital[i];
        }
        // 按成本从小到大
        Arrays.sort(project, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        for (int i = 0; k-- > 0; ) {
            while (i < n && project[i][1] <= w) {
                heap.add(project[i++][0]);
            }
            if (heap.isEmpty()) return w;
            w += heap.poll();
        }

        return w;
    }

}