本题是前缀和 + 贪心判定。
操作只会把练习册从左桌传到右桌,总份数不变,且任何课桌都不能被搬空到 0(因为每次传出要求该桌仍大于 1)。因此最终若存在严格递增数组,则每张桌至少为 1,2,3,…,即:
由于练习册只能向右传、不能向左传,前 k 张桌最终能用到的册子,最多就是它们现在拥有的那些(再往右的桌帮不上忙)。所以:
晚自习教室里有 n 张课桌排成一排。数组 desks 表示每张桌上现在的练习册份数:第 i 张至少有 1 份,不能把哪一张桌完全搬空。
老师要求最后从左到右份数严格递增:对所有合法下标 i,都有 desks[i]<desks[i+1]。
传书只许一种动作:
1 份1 份递给右边邻桌(左边减一、右边加一)可以传任意多次,也可以一次都不传。练习册不能往左边传,也不能凭空多出或少掉。
请判断能不能传成严格递增。
请实现:
canPassBooks(desks: int[]) -> bool
一行:整型数组 desks,形如 [1, 2, 3]。
约束:
true 或 false:能传成严格递增则为 true,否则为 false。
输入:
[1, 2, 3]
输出:
true
说明:已经严格递增,不用传。
输入:
[1, 1, 2]
输出:
false
说明:一共只有 4 份,而三张桌严格递增且每张至少 1 份的最少形态是 1,2,3,需要 6 份。右边的书又不能传回来,所以不可能。
输入:
[10, 1, 1]
输出:
true
说明:左边多出来的练习册可以一路往右传。例如可得到 1,2,9,已经严格递增。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册