502. IPO

    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int curr = 0;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; ++i) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);
        int start = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
        while (k > 0) {
            for (; start < capital.length; start++) {
                if (w >= arr[start][0]) {
                    pq.add(arr[start][1]);
                } else if (w < arr[start][0]) {
                    break;
                }
            }
            if (!pq.isEmpty()) {
                w += pq.poll();
                k--;
            } else {
                break;
            }
        }
        return w;
    }

解题思路：题目要求就是找到每次 小于成本 & 盈利最多 的数据

• 按盈利降序
  1、按盈利降序，循环查找到第一个小于成本的数据就是盈利最多的数据；
  2、循环 K 次，记得排除已经做过的项目

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int[][] arr = new int[profits.length][2];
        for (int i = 0; i < profits.length; ++i) {
            arr[i][0] = profits[i];
            arr[i][1] = capital[i];
        }
        Arrays.sort(arr, (a, b) -> b[0] - a[0]);
        Map<Integer, Boolean> map = new HashMap<>();
        while (k > 0) {
            for (int i = 0; i < arr.length; i++) {
                if (w >= arr[i][1] && !map.containsKey(i)) {
                    w = w + arr[i][0];
                    map.put(i, true);
                    break;
                }
            }
            k--;
        }
        return w;
    }

3、因为每次的循环都是从头开始，所以 超出时间限制 了；

• 按照成本升序 + 最大根堆 求解
  1、按照成本降序，将符合条件的盈利加入到排序队列中，因为是按照成本排序所以之前添加到队列的数据的成本一定低于我的当前成本；
  2、利用有序队列每次从队列中拿出一条数据就是本次的最优数据，不要再次从头遍历，也不用判断当前的数据是不是已经使用过的数据；

• 讲道理我觉得这道题不算困难级别，起码我还有思路；