-
LeetCode高频题84. 柱状图中最大的矩形，单调栈求位置i左边右边距离i最近且比i位置小的位置，然后结算面积
LeetCode高频题84. 柱状图中最大的矩形，单调栈求位置i左边右边距离i最近且比i位置小的位置，然后结算面积
提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
基础知识：
【1】单调栈2：寻找数组arr中i位置左边距离i最近的比i小的位置L，右边距离i最近的比i小的位置R
题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
一、审题
示例：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
输入： heights = [2,4]
输出： 4提示：
1 <= heights.length <=105
0 <= heights[i] <= 104
二、解题
本质上就是求，以每个位置i的柱子为高度h时，咱们能往左右扩出多长的长度来（设为a长度）
面积s=a*h
这就是位置i做高时求得的面积
那你遍历一遍每个位置（N个），每个位置求一个S，将其更新给max
可不就是咱们要的最大的矩形面积吗？这就是解题思路
单调栈确定每个位置i左边距离自己最近，且比自己小的那个位置L，右边距离自己最近且比自己小的位置R
a=R-L-1
比如下图
i=0时，咱们以3做高度h，能扩出最大的矩形是？
左边距离0最近的比3小的位置L=-1，
右边距离0最近的比3小的位置R=1
故矩形底边a=R-L+1=1-（-1）-1=2-1=1所以最大矩形面积是S=a*h=1×3=3
这是以0位置作为高度的情况下，能扩出来的最大矩形
来到每一个位置i，单调栈确定每个位置i左边距离自己最近，且比自己小的那个位置L，右边距离自己最近且比自己小的位置R
这件事情的复杂度，需要o（1）这样才能保证整体复杂度o（n）
这就是本题考你的地方
我之前花了很大心思讲过这个事情
【1】单调栈2：寻找数组arr中i位置左边距离i最近的比i小的位置L，右边距离i最近的比i小的位置R那么就要求咱们提前准备空间，将我们要的LR提前保存好——当然了，如果你代码上要优化的话，另说
coding很巧妙
单调栈：保存下标，规则arri大数压小数，即栈底到栈顶是递增的
arr = 3 2
最开始把0位置（3）压栈自然栈底L=-1
来了一个新的数1位置（2），要满足单调栈的话（我们规定栈底要小，栈顶要要大，懂？），就要把0位置（3）挤出去一旦弹出！结算弹出点的面积
一旦弹出！结算弹出点的面积
一旦弹出！结算弹出点的面积cur=0位置（3），显然此刻，0位置压着的L=-1就是左边距离自己最近，且比3小的位置
显然，是谁让cur弹出的？1位置（2）呗，R=1，它就是距离3最近，且比3小的位置这时候，按照我们上面说的a=R-L-1=1-（-1）-1=1
结算面积S=a×h=1×3=3
更新给max=3，这是我们最好要比N次得到的最大面积
现在你明白了吧，单调栈弹出时立马结算，咱们接着看
多压点数咋搞？
arr = 3 4 5 6 2
最开始把0位置（3）压栈
然后，把1位置（4）压栈
然后，把2位置（5）压栈
然后，把3位置（6）压栈
为啥可以一直压，因为我们规定了单调栈的规则，就是下小，上大
此时，竟然来了4位置（2）
它比栈顶小，显然逼着栈顶们弹出了一旦弹出，就要结算弹出节点cur的面积，更新给max
左边L是谁？栈不空自然就是cur压着那个点，比如cur=3位置（6）
cur压着谁呢？2位置（5），L=2
R是谁？自然就是逼迫cur弹出那个位置，可不就是现在的4位置（2），所以R=4
因此a=R-L-1=4-2-1=1
因此，cur=3位置为高，扩出来最大的矩形面积就是s=a*h=1×6=6
max=6再看4位置（2）能进栈吗？不能
需要弹出栈顶cur=2位置（5）
一旦弹出，就要结算弹出节点cur的面积，更新给max
左边L是谁？栈不空自然就是cur=2压着那个点，
cur压着谁呢？1位置（4），L=1
R是谁？自然就是逼迫cur弹出那个位置，可不就是现在的4位置（2），所以R=4
因此a=R-L-1=4-1-1=2
因此，cur=2位置为高，扩出来最大的矩形面积就是s=a*h=2×5=10
max=10（比之前的6大）再看4位置（2）能进栈吗？不能
需要弹出栈顶cur=1位置（4）
一旦弹出，就要结算弹出节点cur的面积，更新给max
左边L是谁？栈不空自然就是cur=1压着那个点，
cur压着谁呢？0位置（3），L=0
R是谁？自然就是逼迫cur弹出那个位置，可不就是现在的4位置（2），所以R=4
因此a=R-L-1=4-0-1=3
因此，cur=1位置为高，扩出来最大的矩形面积就是s=a*h=3×4=12
max=12（比之前的10大）再看4位置（2）能进栈吗？不能
需要弹出栈顶cur=0位置（3）
一旦弹出，就要结算弹出节点cur的面积，更新给max
左边L是谁？栈不空自然就是cur=0压着那个点，
cur压着谁呢？栈为空，L=-1
R是谁？自然就是逼迫cur弹出那个位置，可不就是现在的4位置（2），所以R=4
因此a=R-L-1=4-（-1）-1=4
因此，cur=0位置为高，扩出来最大的矩形面积就是s=a*h=4×3=12
max=12（不比之前的12大）
如果arr有重复元素怎么办？？？？没关系，依然按照上面的逻辑，不会错过最优解
arr = 3 4 3
0位置（3）进栈，
1位置（4）进栈，来了2位置（3）
迫使1位置（4）进栈弹出cur=1，结算，s=1*4=4
max=4这个按照上面玩就行
但是现在问题来了，2位置（3）进栈吗？因为不是严格递增的不进栈！
让0位置（3）弹出，cur=0，结算
L=-1，R=2
a=2-（-1）-1=2
s=a×h=2×3=6
max=6你这个s=6合理吗？？？？？？
其实你当前2位置的3是可以扩过来的啊
就是说，下面红色格子没问题，你咋就算了个6？？
没关系，我们暂时来了一个次优解这不是，你2位置的3立马要进栈吗？？？
假如现在来了一个3位置（1）
自然你要弹出2位置（3），cur=2，结算
L=-1，R=3
a=R-L-1=3-（-1）-1=3
S=a×h=3×3=9
max=9这个最优解，依然可以被求出来【最优解后续都会出来的】
懂了吧！！！
美滋滋
逻辑你搞清楚了，自然手撕代码问题不大，我们先用纯粹的单调栈解
【1】单调栈2：寻找数组arr中i位置左边距离i最近的比i小的位置L，右边距离i最近的比i小的位置R
需要一个o（n）的方法，提前把arr所有i位置的LR保存好
返回一个二维数组info，info[0]是L，info[1]是R
//单调栈， //一个数，栈为空， 直接往栈里面放，来新数，如果比栈顶大，直接放栈里， //如果和栈顶值相等，则，位置，放在与栈顶的list中， //如果比栈顶值小，则需要结算了， //让栈顶弹出的，当前位置i，就是栈顶右边最近的比栈顶小的位置 //栈顶刚刚压着谁，这个list末尾位置就是栈顶左边最近的最小的位置 //如果栈顶弹出后没有元素了，则，左边最小的位置就设定为-1 //当年所有的位置都访问到arr.len后，单独处理栈中的元素，所有的元素右边最小的位置均为-1，左边看情况，和上面一样 public static int[][] getSubArrayNumWithSingleStack(int[] arr){ int[][] res = new int[arr.length][2]; if (arr == null || arr.length == 0) return res; Stack<List<Integer>> stack = new Stack<>();//单调栈 //挨个遍历所有的元素，O(N)复杂度 for (int i = 0; i < arr.length; i++) { //分三种情况，第一种，新位置的数，比栈顶的值小，要结算了 while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]){ //栈顶是一个list，你得看值，值就是0位置，无所谓的，末尾也行，都相当的 //既然新来的值，小，就要结算，弹出 List<Integer> popIs = stack.pop();//list //我栈顶右边是i，左边得看情况，没压就是-1，压了就是list末尾那个值 int left = stack.isEmpty()? -1 : stack.peek().get(stack.peek().size() - 1);//末尾 for(Integer j:popIs){ res[j][0] = left;//左边最近比栈顶小的位置 res[j][1] = i;//右边最近比栈顶小的肯定是i } } //第2种，新位置的数，比栈顶的值 相等，直接放栈顶那个list if (!stack.isEmpty() && arr[i] == arr[stack.peek().get(0)]){ stack.peek().add(i);//直接放栈顶那个list即可 } //第3种，新位置的数，比栈顶的值 大，新生成list，进栈——很重要 else { ArrayList<Integer> list = new ArrayList<>(); list.add(i); stack.push(list); } }//每一个元素搞定了，i到了arr.len，单独处理剩下栈中的元素 while (!stack.isEmpty()){ //右边全-1，左边看情况 List<Integer> popIs = stack.pop(); int left = stack.isEmpty()? -1 : stack.peek().get(stack.peek().size() - 1); for(Integer j:popIs){ res[j][0] = left; res[j][1] = -1; } } return res; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
当时讲单调栈那会，我讲了重复值怎么解决，那就往栈里面放一个列表，相同arri，把下标们都放进list
然后压栈即可弹出的时候，全部结算，道理一样的
测试：
public static void test2(){ int[] arr = {3,2,1,7,0,4,5,6}; int[][] res = getSubArrayNumWithSingleStack(arr); for (int k = 0; k < arr.length; k++) { for (int i = 0; i < 2; i++) { System.out.print(res[k][i]+" "); } System.out.println(); } } public static void main(String[] args) { test2(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
你看看info是啥？
-1 1 -1 2 -1 4 2 4 -1 -1 4 -1 5 -1 6 -1- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
是不是对的
arr = {3,2,1,7,0,4,5,6};每个位置，左边距离它最近的且比自己小的位置L，右边距离它最近的且比自己小的位置R那会我们讲的时候，认为右边没有就是空，R=-1，现在我们可以认定为R=N位置
都是对的
拿这单调栈的代码，改编为解决本题的代码
//单调栈， //一个数，栈为空， 直接往栈里面放，来新数，如果比栈顶大，直接放栈里， //如果和栈顶值相等，则，位置，放在与栈顶的list中， //如果比栈顶值小，则需要结算了， //让栈顶弹出的，当前位置i，就是栈顶右边最近的比栈顶小的位置 //栈顶刚刚压着谁，这个list末尾位置就是栈顶左边最近的最小的位置 //如果栈顶弹出后没有元素了，则，左边最小的位置就设定为-1 //当年所有的位置都访问到arr.len后，单独处理栈中的元素，所有的元素右边最小的位置均为-1，左边看情况，和上面一样 public static int[][] getSubArrayNumWithSingleStack(int[] arr){ int[][] res = new int[arr.length][2]; if (arr == null || arr.length == 0) return res; int N = arr.length; Stack<List<Integer>> stack = new Stack<>();//单调栈 //挨个遍历所有的元素，O(N)复杂度 for (int i = 0; i < arr.length; i++) { //分三种情况，第一种，新位置的数，比栈顶的值小，要结算了 while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]){ //栈顶是一个list，你得看值，值就是0位置，无所谓的，末尾也行，都相当的 //既然新来的值，小，就要结算，弹出 List<Integer> popIs = stack.pop();//list //我栈顶右边是i，左边得看情况，没压就是-1，压了就是list末尾那个值 int left = stack.isEmpty()? -1 : stack.peek().get(stack.peek().size() - 1);//末尾 for(Integer j:popIs){ res[j][0] = left;//左边最近比栈顶小的位置 res[j][1] = i;//右边最近比栈顶小的肯定是i } } //第2种，新位置的数，比栈顶的值 相等，直接放栈顶那个list if (!stack.isEmpty() && arr[i] == arr[stack.peek().get(0)]){ stack.peek().add(i);//直接放栈顶那个list即可 } //第3种，新位置的数，比栈顶的值 大，新生成list，进栈——很重要 else { ArrayList<Integer> list = new ArrayList<>(); list.add(i); stack.push(list); } }//每一个元素搞定了，i到了arr.len，单独处理剩下栈中的元素 while (!stack.isEmpty()){ //右边全-1，左边看情况 List<Integer> popIs = stack.pop(); int left = stack.isEmpty()? -1 : stack.peek().get(stack.peek().size() - 1); for(Integer j:popIs){ res[j][0] = left; res[j][1] = N; } } return res; } public int largestRectangleArea(int[] heights) { if (heights == null || heights.length == 0) return 0; int max = 0; int N = heights.length; int[][] info = getSubArrayNumWithSingleStack(heights);//单调栈拿到info LR保存好 //遍历arr，求s，更新给max for (int i = 0; i < N; i++) { //i左边距离它最近的且比自己小的位置L，右边距离它最近的且比自己小的位置R int L = info[i][0]; int R = info[i][1]; int a = R - L - 1; int s = a * heights[i]; max = Math.max(max, s); } return max; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
和单调栈上面唯一的区别就是栈顶没有了的时候，R=res[j][1] = N;
我们要的是右边越界位置这样好算a
okay测试：
public static void test2(){ Solution solution = new Solution(); // int[] arr = {3,2,1,7,0,4,5,6}; // // int[][] res = solution.getSubArrayNumWithSingleStack(arr); // for (int k = 0; k < arr.length; k++) { // for (int i = 0; i < 2; i++) { // System.out.print(res[k][i]+" "); // } // System.out.println(); // } int[] arr2 = {2,1,5,6,2,3};//LeetCode测试案例 System.out.println(solution.largestRectangleArea(arr2)); } public static void main(String[] args) { test2(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
结果10
很OKLeetCode测试也非常非常OK
够牛吧？
速度不够快，是因为
下面咱们手撕我们最开始讲的那种方法，在单调栈操作弹出的时候直接结算当前栈顶cur的面积
不要单独求info
直接在i位置小于等于栈顶时，直接弹出栈顶cur，结算
哪怕遇到重复的arri，没关系，先求次优解，问题不大//重复元素不用列表搞，直接弹出，次优解拿住，最优解也不会错过的 public int largestRectangleArea2(int[] heights) { if (heights == null || heights.length == 0) return 0; int max = 0; int N = heights.length; //int[][] info = getSubArrayNumWithSingleStack(heights);//单调栈拿到info LR保存好 //准备单调栈 Stack<Integer> stack = new Stack<>();//放arr的下标哦——规则，栈底小，栈顶大 //遍历arr，压栈，如果遇到更小的弹出cur，求s，更新给max for (int i = 0; i < N; i++) { while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){ //刚刚来的i，比栈顶要小，或者等于，都要弹出，这样可能是次优解，没关系——结算 //i左边距离它最近的且比自己小的位置L，右边距离它最近的且比自己小的位置R int cur = stack.pop();//弹出栈顶 int L = stack.empty() ? -1 : stack.peek();//弹出cur之后没压，那就-1，压了，就是它 int R = i;//谁让栈顶弹出的？i位置呗 int a = R - L - 1; int s = a * heights[cur];//高度就是当前弹出的高度哦，别搞错了 max = Math.max(max, s); } //不进while，那就是正常，要么第一次来，要么就是栈顶还能升序，不管咋样，都要让i进展 stack.push(i); //当arr都放完了，栈还有内容，自然右边就没有数比栈顶小了，R=N } while (!stack.isEmpty()){ int cur = stack.pop();//弹出栈顶 int L = stack.empty() ? -1 : stack.peek();//弹出cur之后没压，那就-1，压了，就是它 int R = N;//谁让栈顶弹出的？i位置呗 int a = R - L - 1; int s = a * heights[cur];//高度就是当前弹出的高度哦，别搞错了 max = Math.max(max, s); } return max; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
中途记住了，进栈前，不断检查，需要弹出就弹出，所以while存在了
不管咋样，弹出结算之后，i必须进栈测试：
public static void test2(){ Solution solution = new Solution(); // int[] arr = {3,2,1,7,0,4,5,6}; // // int[][] res = solution.getSubArrayNumWithSingleStack(arr); // for (int k = 0; k < arr.length; k++) { // for (int i = 0; i < 2; i++) { // System.out.print(res[k][i]+" "); // } // System.out.println(); // } int[] arr2 = {2,1,5,6,2,3};//LeetCode测试案例 System.out.println(solution.largestRectangleArea(arr2)); System.out.println(solution.largestRectangleArea2(arr2)); } public static void main(String[] args) { test2(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
结果
10 10- 1
- 2
LeetCode测试；
很OK吧就这样
单调栈的妙处，懂？
总结
提示：重要经验：1）单调栈那个文章，我讲的很细，用list装重复的arri，这样结算的时候，找那个位置就不会出错
2）对于本题，单调栈，直接干，当i位置<=栈顶，立马弹出栈顶cur，结算搞定
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。 -
相关阅读:
简单学习GoogleColab的入门级概念
[NPUCTF2020]ReadlezPHP 此题有两个flag哦
PTA_乙级_1096
SAP UI5 里的 Busy Indicator 控件使用概述
0037__一文了解嵌入式系统中常用外围接口
DSP28335学习记录（三）——ePWM
WireShark 实践操作
小程序Springboot基层慢性病信息管理系统毕业设计-附源码221550
＜Zero to One＞ ２.perfect competition and monopoly
分析超700万个研发需求发现，这八大编程语言才是行业最需要的
- 原文地址：https://blog.csdn.net/weixin_46838716/article/details/126346580
