香蕉厂最新OA

最近在面试，很需要米来看贴，求大家给加米，谢谢！

新年快到了，亚马逊正在进行促销活动。他们有一份待售商品的价格清单，但可能需要移除其中一些商品。请确定从价格数组中移除的最少商品数量，使得任何k个商品的总价不超过一个设定的阈值。

注意：如果列表中的商品数量小于k，则无需移除任何商品。

示例：

价格 = [3, 2, 1, 4, 6, 5]
k = 3
阈值 = 14
每k = 3个商品的价格总和必须不超过阈值14。最后三个商品的总价格为6 + 5 + 4 = 15。移除价格为6的商品，剩下：

[3, 2, 1, 4, 5]
没有3个商品的总价格超过14。因此只需要移除1件商品。

函数描述：

请完成以下函数

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

：

请完成以下函数获取最大负损益。

获取最大负损益的参数如下：

整数 PnL[数量]: 一个整数数组
返回：

整数: 最大负数数量，使得每个月的累计PnL仍然保持正数
约束条件：

1 ≤ 数量 ≤ 10^5
1 ≤ PnL[i] ≤ 10^9


题不难，但是第二题好多隐藏test case而且不给你看为什么fail比较难。谢谢
最近在面试，很需要米来看帖，求大家给加米，谢谢！

有可能是数组很大，导致timeout，可以试试greedy

1. 
   
2. public static int awsPnL(int[] pnl) {
   
3.         int[] re = {0};
   
4.         awsPnLHelper(0, 0, pnl, 0, re);
   
5.         return re[0];
   
6.     }
   
7. 
   
8.     private static void awsPnLHelper(int lossMonths, int sum, int[] pnl, int i, int[] re) {
   
9.         if (i == pnl.length) {
   
10.             re[0] = Math.max(re[0], lossMonths);
    
11.             return;
    
12.         }
    
13. 
    
14.         for (int sign : new int[]{1, -1} ) {
    
15.             int sum1 = sum + pnl[i] * sign;
    
16.             if (sum1 > 0) {
    
17.                 if (sign == -1 ) {
    
18.                     awsPnLHelper(lossMonths + 1, sum1, pnl, i + 1, re);
    
19.                 } else {
    
20.                     awsPnLHelper(lossMonths , sum1, pnl, i + 1, re);
    
21.                 }
    
22.             }
    
23.         }
    
24.     }
    

复制代码

8 -> 价格[] 大小 数量 = 8
价格 = [9, 6, 3, 2, 9, 10, 11]
3
阈值 = 13
示例输出：
2
解释：
价格为9和7的商品的总和超过13。移除这两件商品后，价格[] = [6, 2, 7, 2]。没有任何商品组合的总价格超过阈值。

价格为7的商品？？和<=13的三件商品只能是《2，3，6》，为啥输出2，我题意理解不对？

第一题用heap做会timeout吗？