本题是Leetcode刚上新，还没来得及翻译的会员中等题，用到的知识点是最小堆。
3711. Maximum Transactions Without Negative Balance
You are given an integer array transactions, where transactions[i] represents the amount of the ith transaction:
- A positive value means money is received.
- A negative value means money is sent.
The account starts with a balance of 0, and the balance must never become negative. Transactions must be considered in the given order, but you are allowed to skip some transactions.
Return an integer denoting the maximum number of transactions that can be performed without the balance ever going negative.
Example 1:
Input: transactions = [2,-5,3,-1,-2]
Output: 4
Explanation:
One optimal sequence is [2, 3, -1, -2], balance: 0 → 2 → 5 → 4 → 2.
Example 2:
Input: transactions = [-1,-2,-3]
Output: 0
Explanation:
All transactions are negative. Including any would make the balance negative.
Example 3:
Input: transactions = [3,-2,3,-2,1,-1]
Output: 6
Explanation:
All transactions can be taken in order, balance: 0 → 3 → 1 → 4 → 2 → 3 → 2.
Constraints:
1 <= transactions.length <= 10**5-10**9 <= transactions[i] <= 10**9
这是我的Ruby解
# @param {Integer[]} transactions
# @return {Integer}
def max_transactions(transactions)
len = transactions.length
accepted = Containers::MinHeap.new
positive = []
num = 0
i = 0
while i < len
if transactions[i] >= 0
num += transactions[i]
positive << transactions[i]
elsif num + transactions[i] >= 0
num += transactions[i]
accepted.push(transactions[i])
elsif num + transactions[i] < 0
if accepted.size > 0 && accepted.min < transactions[i]
num += (accepted.pop).abs
num += transactions[i]
accepted.push(transactions[i])
end
end
i += 1
end
positive.length + accepted.size
end
