【每日一题】LeetCode 84. Largest Rectangle in Histogram

[@haodongqi2907]

这个one pass真的太强了，看完感觉对于单调栈的理解更深了

[@Wahkit]

太强了...之前参考lc的答案 要做两次pass..步骤有点繁琐而且理解起来有点费劲。这个方法就很清晰。谢谢指导

[@PeterPeng-xc2sk]

太精妙了，感谢老师

[@stevenguo9060]

这么快更新了，听了2334回来一看这个题都更新好了

[@stevenguo9060]

不过preSmaller和nextSamller可以在一个循环中更新
Stack stack = new Stack();
for(int i=0; i nums[i]){
nextSmaller[stack.pop()] = i;//栈顶元素的nextSmaller是新元素
}
if(!stack.isEmpty()) preSmaller[i] = stack.peek(); //新元素的preSmaller是栈顶元素
stack.push(i);
}

[@Eeeason-c5y]

3 pass推導至1 pass的過程太精彩了！！！

[@meteorv3447]

您好，關於
vectornextSmaller(n, n);
vectorprevSmaller(n, -1);
這兩個 vector 的初始值的部分，聽講解會覺得設定 n 和 -1 好像很自然
並且也都能讓一些找不到 next smaller & prev smaller 的都恰好能得到正確的寬度
但自己想的時候，好像會有點說服不了自己為何該設定這個值
想請問這是固定用法 還是有沒有其他緣由呢 ?

[@wisdompeak]

这是一个常见的trick。你也可以自定义一个值比如说MAX_INT表示无解，只要自己的code在处理的时候能考虑到这类情况即可。

[@MengqiZhou]

Three pass的解法里面得到的prev_smaller难道不应该是prev_smaller_or_equal吗？因为被弹走得是larger element,那剩下的就是smaller or equal, 而不仅仅是smaller？

[@wisdompeak]

是的

[@MengqiZhou]

@@wisdompeak 那似乎需要证明一下prev equal的合理性啊，虽然solution是对的

[@wisdompeak]

@@MengqiZhou 不好意思，我之前的回复没有仔细考虑。你看的是我github上的three pass的代码吗？那个确实是prevSmaller。当因为heights[stk.top()] > heights[i]弹出栈顶元素的时候，nums[i]确实就是栈顶元素的prevSmaller而不可能是equal。

[@MengqiZhou]

@@wisdompeak 谢谢回复！表达不畅，比如heights = [1, 1], 如果用three pass的代码，得到的prevSmaller = [-1, 0], 也就是说heights第二个元素（i= 1， heights[1] 是 1）的prevSmaller是第一个元素（p'revSmllaler[1] = 0,), 而这个prevSmaller其实是equal（ heights[0]也是1）

[@wisdompeak]

@@MengqiZhou 哦，你看的是视频里18:06 L27的代码。那个地方确实应该是指prevSmallerOrEqual，从逻辑上讲这样写是有瑕疵的（应该求prevSmaller）。至于为什么能AC，可以看你的那个例子。我们考虑第二个柱子的时候，按照这种有瑕疵的算法，面积算的是1. 但是考虑第一个柱子的时候，面积算出的是2. 可见，只要我们求的最大面积，必然有一个hieghts[i]（尽量靠左边）是符合要求的。

[@yw2985]

请问如何加入刷题群？

[@wisdompeak]

board.cruelcoding.com

[@thelearner3962]

这我真的想不到啊啊啊啊啊啊