单调栈

举报
兔老大 发表于 2021/04/25 01:13:47 2021/04/25
【摘要】 通过使用栈这个简单的结构,我们可以巧妙地降低一些问题的时间复杂度。 单调栈性质: 1、若是单调递增栈,则从栈顶到栈底的元素是严格递增的。若是单调递减栈,则从栈顶到栈底的元素是严格递减的。 2、越靠近栈顶的元素越后进栈。(显而易见) 本文介绍单调栈用法 通过一道题来说明。 POJ2559 1. 题目大意:链接 给出一个柱形统计图(histogram), 它的每个...

通过使用栈这个简单的结构,我们可以巧妙地降低一些问题的时间复杂度。

单调栈性质:

1、若是单调递增栈,则从栈顶到栈底的元素是严格递增的。若是单调递减栈,则从栈顶到栈底的元素是严格递减的。

2、越靠近栈顶的元素越后进栈。(显而易见)

本文介绍单调栈用法

通过一道题来说明。

POJ2559

1. 题目大意:链接

给出一个柱形统计图(histogram), 它的每个项目的宽度是1, 高度和具体问题有关。 现在编程求出在这个柱形图中的最大面积的长方形。

7 2 1 4 5 1 3 3
 

7表示柱形图有7个数据,分别是 2 1 4 5 1 3 3, 对应的柱形图如下,最后求出来的面积最大的图如右图所示。

做法1:枚举每个起点和终点,矩形面积就是长*最小高度。O(N^3)

做法2:区间最小值优化。O(N^2)

做法3:以每一个下标为中心向两边扩,遇到更短的就停,这样我们可以确定以每一个下标高度为最高的矩形。O(N^2)

单调栈:维护一个单调递增栈,所有元素各进栈和出栈一次即可。每个元素出栈的时候更新最大的矩形面积。

过程:

1)判断当前元素小于栈顶

2)条件满足,就可以更新栈顶元素的最大长度了,并且把栈顶弹出

3)继续执行(1),直到条件不满足。

 

重要结论:

1)栈顶下面一个元素一定是,栈顶左边第一个比栈顶小的元素

2)当前元素一定是,右边第一个比栈顶小的元素。

为什么呢?

比如这是个栈

1)如果右边存在距离更近的比1号小的数,1号早已经弹出了。

2)如果左边有距离更近的比1号小的数

                如果它比2号小,它会把2号弹出,自己成为2号

                 如果它比2号大,它不会弹出2号,但是它会压栈,变成2号,原来的2号成为3号。

所以不管怎么说,这个逻辑是正确的。

最后放代码并讲解

 

下面看一道难一些的题

LeetCode 85 Maximal Rectangle

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 6.二三行后面那六个1

 

给定一个由二进制组成的矩阵map,找到仅仅包含1的最大矩形,并返回其面积。

这道题是一行一行的做。对每一行都求出每个元素对应的高度,这个高度就是对应的连续1的长度,然后对每一行都更新一次最大矩形面积。

连续1长度也很好更新,本个元素是0,长度就是0,本个元素是1,那就加上之前的。

具体思路代码中讲解。


  
  1. import java.util.Stack;
  2. public class MaximalRectangle {
  3. public static int maxRecSize(int[][] map) {
  4. if (map == null || map.length == 0 || map[0].length == 0) {
  5. return 0;
  6. }
  7. int maxArea = 0;
  8. int[] height = new int[map[0].length];
  9. for (int i = 0; i < map.length; i++) {
  10. for (int j = 0; j < map[0].length; j++) {
  11. height[j] = map[i][j] == 0 ? 0 : height[j] + 1;//0长度为0,1长度为前面+1
  12. }
  13. maxArea = Math.max(maxRecFromBottom(height), maxArea);//调用第一题的思想
  14. }
  15. return maxArea;
  16. }
  17. //第一题思路
  18. public static int maxRecFromBottom(int[] height) {
  19. if (height == null || height.length == 0) {
  20. return 0;
  21. }
  22. int maxArea = 0;
  23. Stack<Integer> stack = new Stack<Integer>();
  24. for (int i = 0; i < height.length; i++) {
  25. //栈非空并且栈顶大
  26. while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
  27. int j = stack.pop();//弹出
  28. int k = stack.isEmpty() ? -1 : stack.peek();
  29. int curArea = (i - k - 1) * height[j];//计算最大
  30. maxArea = Math.max(maxArea, curArea);//更新总体最大
  31. }
  32. stack.push(i);//直到栈顶小,压入新元素
  33. }
  34. //最后栈非空,右边没有更小元素使它们弹出
  35. while (!stack.isEmpty()) {
  36. int j = stack.pop();
  37. int k = stack.isEmpty() ? -1 : stack.peek();
  38. int curArea = (height.length - k - 1) * height[j];
  39. maxArea = Math.max(maxArea, curArea);
  40. }
  41. return maxArea;
  42. }
  43. public static void main(String[] args) {
  44. int[][] map = { { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 0 }, };
  45. System.out.println(maxRecSize(map));
  46. }
  47. }

 

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/82717317

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200