# 2599. Make the Prefix Sum Non-negative
###### tags: `Leetcode` `Medium` `Prefix Sum` `Priority Queue` `Greedy`
Link: https://leetcode.com/problems/make-the-prefix-sum-non-negative/description/
## 思路
先算prefix sum 如果prefix sum小于0 执行一次operation 把前面数字里面最小的拿出来 从prefix sum里面减掉 直到遍历完整个array
这时候可能会想为什么我们不用再遍历一遍那些被加到尾部的数字
因为那些数字肯定都是负数 既然整个array所有数字的和是non-negative 那么再遍历一遍这些数字得到的每一个prefix sum肯定也都是non-negative number
## Code

class Solution {
    public int makePrefSumNonNegative(int[] nums) {
        Queue<Integer> pq = new PriorityQueue<>();
        long currSum = 0;
        for(int num:nums){
            currSum += num;
            pq.add(num);
            if(currSum<0){
                currSum -= pq.poll();
            }
        }
        return nums.length-pq.size();
    }
}