[回复加米] Hackerrank 招聘会 OA 求个解法

Hackerrank career fair的一道题。

一列数组表示一串箱子能承重几个箱子。每

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

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

不能分割。

哪位朋友如果有解法我给反复加大米。

greedy，排序后堆模拟，倒着堆放，我们只在意每个stack长度，所以堆里放长度即可。当最短的stack也无法承受，就开一个新的stack放入堆。

时间复杂度 O(nlogn)

1. import java.util.*;
   
2. 
   
3. class Solution {
   
4.     public static void main(String[] args) {
   
5.         System.out.println(minStack(new int[] {3, 1, 2, 3, 0, 0}));  // 2
   
6.         System.out.println(minStack(new int[] {1, 0, 0, 0, 0, 0}));  // 5
   
7.         System.out.println(minStack(new int[] {3, 0, 3, 0, 0, 0}));  // 4
   
8.         System.out.println(minStack(new int[] {0, 1, 2, 3, 4, 5}));  // 1
   
9.     }
   
10.     public static int minStack(int[] nums) {
    
11.         var pq = new PriorityQueue<Integer> ();
    
12.         Arrays.sort(nums);
    
13.         for (int num: nums) {
    
14.             if (pq.isEmpty() || pq.peek() > num) {
    
15.                 pq.offer(1);
    
16.             } else if (pq.peek() <= num) {
    
17.                 int weight = pq.poll();
    
18.                 pq.offer(weight + 1);
    
19.             }
    
20.         }
    
21.         return pq.size();
    
22.     }
    
23. }

复制代码

我已全仓 发表于 2021-9-14 16:06
greedy，排序后堆模拟，倒着堆放，我们只在意每个stack长度，所以堆里放长度即可。当最短的stack也无法承受 ...

豁然开朗！多谢，大米给您加满