关于单调栈
  • 板块学术版
  • 楼主Kniqht
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/11/8 17:55
  • 上次更新2023/11/8 19:51:03
查看原帖
关于单调栈
315205
Kniqht楼主2023/11/8 17:55

比如给定一个由 0/1 字符组成的矩阵,我们要求出最大的只由 0 组成的子矩阵的大小。

然后我们可以使用单调栈对吧?我们枚举一条横线,然后用单调栈求出以这个线为底的最大长方形

但是这个怎么做啊?我看网上都是说“统计每个点往上能延伸的"高度",之后维护高度递增的单调栈,之后当其出栈的时候统计面积”

但是遇到一行是这种情况时(就是往上延伸的高度):2 1 1

先2入栈,然后1比2小,2出栈,然后这时候统计答案,ans=max(ans,2),然后下一个1入栈,最后统计答案ans=max(ans,2)。

但是很明显211这种情况答案应该为3啊?这种情况怎么解决呢?

2023/11/8 17:55
加载中...