单调栈的定义：
单调栈是栈的一中特殊形式，在栈中的元素必须满足单调性（一定是单调上升或单调下降等等的规律）。
单调栈的性质：
单调栈解决的常见问题：给定一个序列，求每个位置左边，离他最近且小于他的数的位置。
我们可以这样理解单调栈：
既然我们必须让元素满足单调性，那么每次插入就和栈顶作比较。
如果不满足某些性质，直接弹出栈顶，直到栈为空或满足该性质插入这个元素。
单调递增栈：在保持栈内元素单调递增的前提下（如果栈顶元素大于要入栈的元素，将将其弹出），将新元素入栈。
单调递减栈：在保持栈内元素单调递减的前提下（如果栈顶元素小于要入栈的元素，则将其弹出），将新元素入栈。
单调栈练习题汇总
- 已解决
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;}
}
