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;
}
当时讲单调栈那会，我讲了重复值怎么解决，那就往栈里面放一个列表，相同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();
}
你看看info是啥？
-1 1
-1 2
-1 4
2 4
-1 -1
4 -1
5 -1
6 -1
是不是对的
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;
}
和单调栈上面唯一的区别就是栈顶没有了的时候，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();
}
结果10
很OK
LeetCode测试也非常非常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;
}
中途记住了，进栈前，不断检查，需要弹出就弹出，所以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();
}
结果
10
10
LeetCode测试；
很OK吧
就这样
单调栈的妙处，懂？
总结
提示：重要经验：
1）单调栈那个文章，我讲的很细，用list装重复的arri，这样结算的时候，找那个位置就不会出错
2）对于本题，单调栈，直接干，当i位置<=栈顶，立马弹出栈顶cur，结算搞定
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。