利口原题脸书电面

上个星期四面的，贰叁扒，斯贰
都是有阵子之前刷过的，第一题很快过，第二题正在跟对方描述想法，被对方打断并且要我把第二题当作第一题的follow up用

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

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

的国人美眉了
所以脸书也不是一定要两题bugfree，可能一题半也够了....

我没看答案的时候想到的就是没用stack的，这个解法需要更多额外空间，时间复杂度跟stack解法一样，所以还是stack解法更好一些
我的代码：

1. public class Solution
   
2.     {
   
3.         public int Trap(int[] height)
   
4.         {
   
5.             var leftMax = new int[height.Length];
   
6.             leftMax[0] = height[0];
   
7.             for (var i = 1; i < height.Length; ++i)
   
8.             {
   
9.                 leftMax[i] = Math.Max(leftMax[i - 1], height[i]);
   
10.             }
    
11. 
    
12.             int rightMax = 0, sum = 0;
    
13.             for (var i = height.Length - 1; i >= 0; --i)
    
14.             {
    
15.                 rightMax = Math.Max(rightMax, height[i]);
    
16.                 var vol = Math.Min(leftMax[i], rightMax) - height[i];
    
17.                 sum += vol > 0 ? vol : 0;
    
18.             }
    
19. 
    
20.             return sum;
    
21.         }
    
22.     }

复制代码

[/i][/i][/i][/i][/i]

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

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

JoyForce 发表于 2021-2-2 06:21
不知道你说的双指针是啥意思，我觉得双指针没法解这道题，可否贴出思路或者代码？
我的解法里，要扫两遍， ...

你只用记录left_max和right_max就行了

https://leetcode-cn.com/problems ... -by-fight_for_your/

Two Pointer solution?

害群之蚂蚁 发表于 2021-2-2 05:38
Two Pointer solution?

不清楚two pointer怎么做，两题都可以左到右扫一遍再右到左扫一遍记录局部乘积/running max，然后再计算结果

JoyForce 发表于 2021-2-2 05:52
我没看答案的时候想到的就是没用stack的，这个解法需要更多额外空间，时间复杂度跟stack解法一样，所以还是 ...

不会啊双指针解法space是O(1)
stack是O(N)

有种做爱还要换姿势的感觉， 姿势不正确好走不送。

denghuixing 发表于 2021-02-01 14:10:40
不会啊双指针解法space是O(1)
stack是O(N)

不知道你说的双指针是啥意思，我觉得双指针没法解这道题，可否贴出思路或者代码？
我的解法里，要扫两遍，扫第一遍的时候要把最大值记录下来，需要额外O(N)空间

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

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

楼主很厉害了，要是我就懵了，哈哈哈