3711. 不出现负余额的最大交易额 🔒

题目描述

给定一个整数数组 transactions，其中 transactions[i] 表示第 i 笔交易的总额：

正值表示收到的钱。
负值表示支付的钱。

账户初始余额为 0，且余额 必须始终保持非负。交易必须按照给定的顺序进行处理，但你可以跳过一些交易。

返回一个整数，表示在不使余额变为负数的情况下可以执行的 最大交易次数。

示例 1：

输入：transactions = [2,-5,3,-1,-2]

输出：4

解释：

一个最优序列是 [2, 3, -1, -2]，余额：0 → 2 → 5 → 4 → 2。

示例 2：

输入：transactions = [-1,-2,-3]

输出：0

解释：

所有交易均为负数。进行任何一项交易都会使余额变为负数。

示例 3：

输入：transactions = [3,-2,3,-2,1,-1]

输出：6

解释：

所有交易都可以按顺序进行，余额：0 → 3 → 1 → 4 → 2 → 3 → 2。

提示：

1 <= transactions.length <= 10⁵
-10⁹ <= transactions[i] <= 10⁹

解法

方法一：贪心 + 有序集合

我们使用一个有序集合（如 C++ 的 multiset，Java 的 TreeMap，Python 的 SortedList）来存储已经选择的交易金额，并维护一个变量 \(s\) 来记录当前的余额。初始时 \(s=0\)，答案 \(\textit{ans}\) 初始化为交易次数。

然后我们遍历每笔交易金额 \(x\)：

将 \(x\) 加到余额 \(s\) 中，并将 \(x\) 添加到有序集合中。
如果此时余额 \(s\) 变为负数，说明当前选择的交易金额中有一些负数金额导致余额不足。为了尽可能保留更多的交易，我们应该移除当前选择的交易金额中最小的那个金额（因为移除最小的金额可以最大化余额）。我们从有序集合中移除最小的金额 \(y\)，并将 \(y\) 从余额 \(s\) 中减去，同时将答案 \(\textit{ans}\) 减 \(1\)。
重复步骤 2，直到余额 \(s\) 不再为负数。

遍历完成后，答案 \(\textit{ans}\) 即为最多可以进行的交易次数。

时间复杂度 \(O(n \times \log n)\)，其中 \(n\) 是交易次数。空间复杂度 \(O(n)\)。

Python3JavaC++Go

class Solution:
    def maxTransactions(self, transactions: List[int]) -> int:
        st = SortedList()
        s = 0
        ans = len(transactions)
        for x in transactions:
            s += x
            st.add(x)
            while s < 0:
                y = st.pop(0)
                s -= y
                ans -= 1
        return ans

class Solution {
    public int maxTransactions(int[] transactions) {
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        int ans = transactions.length;
        long s = 0;
        for (int x : transactions) {
            s += x;
            tm.merge(x, 1, Integer::sum);
            while (s < 0) {
                int y = tm.firstKey();
                s -= y;
                --ans;
                if (tm.merge(y, -1, Integer::sum) == 0) {
                    tm.remove(y);
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int maxTransactions(vector<int>& transactions) {
        multiset<int> st;
        int ans = transactions.size();
        long long s = 0;
        for (int x : transactions) {
            s += x;
            st.insert(x);
            while (s < 0) {
                auto it = st.begin();
                int y = *it;
                st.erase(it);
                s -= y;
                --ans;
            }
        }
        return ans;
    }
};

func maxTransactions(transactions []int) int {
    tm := redblacktree.New[int, int]()
    ans := len(transactions)
    var s int64

    for _, x := range transactions {
        s += int64(x)
        if cnt, ok := tm.Get(x); ok {
            tm.Put(x, cnt+1)
        } else {
            tm.Put(x, 1)
        }

        for s < 0 {
            it := tm.Iterator()
            it.Begin()
            it.Next()
            y := it.Key()
            s -= int64(y)
            ans--

            cnt, _ := tm.Get(y)
            if cnt == 1 {
                tm.Remove(y)
            } else {
                tm.Put(y, cnt-1)
            }
        }
    }
    return ans
}

3711. 不出现负余额的最大交易额 🔒

题目描述

解法

方法一：贪心 + 有序集合

评论