狗VO

五轮，第一轮BQ，其他四轮technical

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

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

刚才想了一下，根本不需要单调栈，直接对这些点找左右边界即可，傻了

1. 
   
2. public boolean[] isDry(int[] height, int[] fountains) {
   
3.         if (height == null || height.length == 0) {
   
4.             return new boolean[0];
   
5.         }
   
6.         int n = height.length;
   
7.         boolean[] isWet = new boolean[n];
   
8.         for (int x: fountains ) {
   
9.             int j = x;
   
10.             while (j < n && height[j] <= height[x]) {
    
11.                j++;
    
12.             }
    
13.             int i = x;
    
14.             while (i >= 0 && height[i] <= height[x]) {
    
15.                 i--;
    
16.             }
    
17.             for (int k = i + 1; k < j; k++) {
    
18.                 isWet[k] = true;
    
19.             }
    
20.         }
    
21. 
    
22.         return isWet;
    
23.     }
    

复制代码

第二轮 碰到喷泉单调栈往左找，记住当前喷泉高度继续往右，小于高度的直接mark掉。一遍就行
第三轮，unionfind,保存每块棋子的气的数量，变为零就是死了
第四轮，3个TreeMap或者PQ。因为有5分钟的条件，我觉得要把所有5分钟的数存起来，做成对象，然后删除超时对象，并重新计算topK和bottomK。由于有删除操作，PQ可能不行，用TreeMap比较好。

kashimoto 发表于 2021-06-15 14:14:00
请教一下棋盘那题的followup 判断棋子是否被吃掉时间复杂度为O(1） 如何实现O(1)的判断呢

我是用的union find, 并且维护每个connected component 还有多少个空缺的位置才会被吃掉

第一个题目没说什么是干的，怎么做

Falldawn 发表于 2021-6-16 04:58
第一个题目没说什么是干的，怎么做

高低差吧 类似流水问题

喷泉那题我感觉不用排序吧 如果当前是喷泉的话 单调栈直接pop前面那些高度小于当前高度的  然后后面的高度小于喷泉的不用入栈，等到下一个更高的地方重置

请教一下棋盘那题的followup 判断棋子是否被吃掉时间复杂度为O(1） 如何实现O(1)的判断呢

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

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

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

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

第一题类似扫描线吧.

在X的时候+1， 在X + 2 + 2k的位置-1.

然后loop一遍，记录所有 == 0的位置.

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

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