单调栈是一种特殊的栈数据结构,在栈的基础上增加了一些特定的性质。它主要用于解决一类与元素大小和顺序有关的问题。
class Solution {
public int trap(int[] height) {
int res = 0;
// 高度
int h = 0;
// 宽度
int w = 0;
// 构造递增的单调栈
Stack<Integer> stk = new Stack<>();
stk.push(0);
for(int i = 1; i < height.length; i++){
if(height[i] <= height[stk.peek()]) stk.push(i);
else{
while(!stk.empty() && height[i] > height[stk.peek()]){
int base_position = stk.pop();
if(!stk.empty()){
w = i - stk.peek() - 1;
h = Math.min(height[i], height[stk.peek()]) - height[base_position];
res += w * h;
}
}
stk.push(i);
}
}
return res;
}
}
单调栈作用:记录遍历过且没有被计算的元素下标
单调栈顺序:降序(栈底小)
特别要求: 需要在首尾元素前后各增加0
场景:
① heights[i] > heights[st.peek()] — while循环 — 栈顶元素左右两侧的第一个比他小的元素分别是 heights[i] 和 栈内的下一个元素
int base = stk.pop();
if(!stk.empty()){
res = Math.max(res, h[base] * (i - stk.peek() - 1));
}
② heights[i] <= heights[st.peek()] — 构造出了下降栈
st.push(i)
class Solution {
public int largestRectangleArea(int[] heights) {
int[] h = new int[heights.length+2];
// 补0,防止死循环或者空栈错误
for(int i = 1; i < heights.length+1; i++){
h[i] = heights[i-1];
}
int res = 0;
// 降序,要找下一个比他小的,栈底小
Stack<Integer> stk = new Stack<>();
stk.push(0);
for(int i = 1; i < h.length; i++){
if(h[i] >= h[stk.peek()]) stk.push(i);
else{
while(!stk.empty() && h[i] < h[stk.peek()]){
int base = stk.pop();
if(!stk.empty()){
// 此处求最大包含面积时候,
// 左右两次第一次比他小的位置只作为限制范围,
// 不计入真实面积的计算范围
res = Math.max(res, h[base] * (i - stk.peek() - 1));
}
}
stk.push(i);
}
}
return res;
}
}