当前位置：首页 > article >正文

一文解决单调栈的应用

article 2025/3/3 18:01:31

单调栈的定义：

单调栈是栈的一中特殊形式，在栈中的元素必须满足单调性（一定是单调上升或单调下降等等的规律）。

单调栈的性质：

单调栈解决的问题

单调栈解决的常见问题：给定一个序列，求每个位置左边，离他最近且小于他的数的位置。
我们可以这样理解单调栈：
既然我们必须让元素满足单调性，那么每次插入就和栈顶作比较。
如果不满足某些性质，直接弹出栈顶，直到栈为空或满足该性质插入这个元素。

如何维护一个单调栈

单调递增栈：在保持栈内元素单调递增的前提下（如果栈顶元素大于要入栈的元素，将将其弹出），将新元素入栈。
单调递减栈：在保持栈内元素单调递减的前提下（如果栈顶元素小于要入栈的元素，则将其弹出），将新元素入栈。

单调栈的规律

在这里插入图片描述

单调栈练习题汇总

已解决

1 模拟单调栈
2 leetocde T84柱形图中的最大矩形
未完待续

模拟单调栈

分析

本题是单调栈的模板题，可以用数组模拟单调栈，但是我个人更喜欢用Stack集合调用API的方式。

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] q = new int[n + 1];
        Stack<Integer> stk = new Stack<>();
        
        for(int i = 0; i < n; i++) q[i] = sc.nextInt();
        for(int i = 0; i < n; i++) {
            while(!stk.empty() && q[stk.peek()] >= q[i]) stk.pop();
            if(stk.empty()) System.out.print("-1 ");
            else System.out.print(q[stk.peek()] + " ");
            stk.push(i);
        }
    }
}

柱形图中的最大矩形

题目分析：

本题中在该柱状图中，求能够勾勒出来的矩形的最大面积这个问题，可以模拟样例，想一想如何解决这个面积问题？
首先对于面积，需要底×高，高度跟每个柱子的高度有关，底和对应柱子的下标有关系。正确的思路是枚举每个柱子的高度，以这个高度向左右两边进行扩展，如果能找到当前柱子左右两边的离他最近且小于他的高度的柱子,那么这个柱子所能构成的最大矩形面积就是用当前的柱子的高度h[i] * (right[i] - left[i] - 1)

为什么要减1？
right[i] - left[i]：这是从 left[i] 到 right[i] 之间的距离，但这包括了left[i]和 right[i] 本身。
我们真正关心的是柱子 i 左边和右边，第一个小于它的柱子之间的距离，所以不包括 left[i] 和 right[i]，而是 left[i] 和 right[i] 之间的元素个数。因此，要在 right[i] - left[i] 的基础上再减去 1。
举例：
假设 heights = [2, 1, 5, 6, 2, 3]，我们考察柱子i = 2(即高度为 5 的柱子):
left[2] = 1：在 heights[2] 左边，第一个小于 5 的柱子在索引 1。
right[2] = 4：在 heights[2] 右边，第一个小于 5 的柱子在索引 4。
所以 right[2] - left[2] - 1 = 4 - 1 - 1 = 2。
这表示柱子 i = 2 的宽度为 2（包括自己）时，高度为 5 的矩形面积最大。因此，面积为 heights[2] * (right[2] - left[2] - 1) = 5 * 2 = 10。

代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Stack<Integer> stk = new Stack<>();
        int[] left = new int[n + 1];
        int[] right = new int[n + 1];

        
        for(int i = 0; i < n; i++) {
            while(!stk.empty() && heights[stk.peek()] >= heights[i]) stk.pop();
            if(stk.empty()) left[i] = -1;
            else left[i] = stk.peek();

            stk.push(i); 
        }
        stk.clear();

        // 维护当前元素的右边比自己小的最近的数的下标 
        for(int i = n - 1; i >= 0; i--) {
            while(!stk.empty() && heights[stk.peek()] >= heights[i]) stk.pop();
            if(stk.empty()) right[i] = n;
            else right[i] = stk.peek();

            stk.push(i);
        }

        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));
        }

        return ans;
    }
}