力扣hot100 柱状图中最大的矩形 单调栈

Problem: 84. 柱状图中最大的矩形

思路

👨‍🏫 参考地址

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(n)$

Code

class Solution {public static int largestRectangleArea(int[] height){Stack<Integer> stack = new Stack<Integer>();// 单调递增栈 存的是下标int n = height.length;int[] h = new int[n + 2];//加两 哨兵节点，因为是单调递增栈 所以 加最小值h[0] = 0;//前哨兵System.arraycopy(height, 0, h, 1, n);//把 height 数组 从 0 开始 复制长度为 [1,n] (n-1 + 1)的长度到 h 数组h[n + 1] = 0;//后哨兵int m = n + 2;int ans = 0;for (int i = 0; i < m; i++){while (!stack.isEmpty() && h[i] < h[stack.peek()]){int cur = stack.pop();//这是区间的最小值,现在 i 并没有入栈// 至此：h(l，r)开区间内都是 大于 h[cur]int l = stack.peek() + 1;// 当前栈顶为左边的第一个小于 h[cur] 的值 的下标ans = Math.max(ans, (i - l) * h[cur]);}
//			stack.push(i);stack.add(i);}return ans;}
}