单调栈
概念
单调栈是一种数据结构，在栈结构上增加了数据特征，数据特征分别有单调递增性和单调递减性。单调递增栈即栈中的元素或者关联属性保持递增。单调递减栈即栈中的元素或者关联属性保持递减。
实现
// 重点：单调栈保持单调性的操作是在入栈时与栈顶比较，不符合条件则将栈顶出栈直到满足条件再入栈
class MonotoneStack<T> {
constructor() {}
public data: T[] = [];
get top() {
return this.data.length;
}
get isEmpty() {
return this.top === 0;
}
get topElement() {
if (!this.top) return undefined;
return this.data[this.top - 1];
}
pop() {
return this.data.pop();
}
push(elem: T, ...args: any[]) {
throw 'Must implement `push` method!';
}
clear() {
this.data.length = 0;
return this.data;
}
}
// 单调递增
class MonotoneIncreaseStack extends MonotoneStack<number> {
constructor() { super() }
push(elem: number, iterator: (elem: number) => void = function() {}) {
while(this.data.length && this.topElemen > elem) {
iterator.call(this, this.data.pop());
}
this.data.push(elem);
}
}
// 单调递减
class MonotoneDecreaseStack extends MonotoneStack<number> {
constructor() { super() }
push(elem: number, iterator: (elem: number) => void = function() {}) {
while(this.data.length && this.topElemen < elem) {
iterator.call(this, this.data.pop());
}
this.data.push(elem);
}
}
特性
- 栈的基本属性，后进先出（LIFO，last-in first-out）；
- 栈里的元素（或者元素关联属性）具备单调性，递增或递减；
- 假设 f 为求出离 i 最近比自己大的数或者自己小的数，f(i)总是在 i-1, f(i-1), f(f(i-1))…中取值；
- 即，当 i 入栈之前栈中的数据满足如下规律，i-1, f(i-1), f(f(i-1))…；
- 假定一个区间入栈到单调栈中，栈中元素具备区间极值到右边区间的单调性；
- 将区间逐个入栈到单调递减栈中，栈中元素为满足区间最大值到区间最右值逐个递减；
- 将区间逐个入栈到单调递增栈中，栈中元素为满足区间最小值到区间最右值逐个递增；
补充说明
从图片归纳 3、4 点特性，假设有一串正整数 3 10 5 7 3 2 6 4 0.5 1 5 7，1~10已入单调递减栈栈，先准备入栈的是 11
图中 11 左边距离最小且比自己小的值，在图中连线的元素查找，即 10, f(10) = 8, f(8) = 7, f(7) = 4, f(4) = 2，经过比较 7 的值比 11 大且距离最近。已入栈的区间为 2~10，从图中可以看出栈中保留了元素使 2 4 7 8 10，2为最大值并递减到1。
图中11入栈时会把 8 9 10 弹出，新的栈中元素连线如下。
应用
1. 柱状图最大矩形面积
- 题目链接 ref
- 代码实现
class MonotoneStack<T> {
constructor() {}
public data: T[] = [];
get top() {
return this.data.length;
}
get isEmpty() {
return this.top === 0;
}
get topElement() {
if (!this.top) return undefined;
return this.data[this.top - 1];
}
pop() {
return this.data.pop();
}
push(elem: T, ...args: any[]) {
throw 'Must implement `push` method!';
}
clear() {
this.data.length = 0;
return this.data;
}
}
class MonotoneIncreaseStack extends MonotoneStack<number> {
constructor(source: number[]) {
super();
this.source = source;
}
public source: number[]
push(elem: number, iterator: (elem: number) => void = function() {}) {
while(this.data.length && this.source[this.topElement] > this.source[elem]) {
iterator.call(this, this.data.pop());
}
this.data.push(elem);
}
}
class LargestRectangleArea extends MonotoneIncreaseStack {
constructor(heights: number[]) {
super(heights);
this.source = this.source.slice(0);
this.source.unshift(0);
this.source.push(0);
}
run() {
return this.source.reduce((acc, elem, i) => {
this.push(i, function(cur) {
acc = Math.max(acc, (i - this.topElement - 1) * this.source[cur]);
});
return acc;
}, 0);
}
}
function largestRectangleArea(heights: number[]): number {
return (new LargestRectangleArea(heights)).run();
};
2. 接雨水
- 题目链接 ref
- 代码实现
class MonoStack<T> {
constructor() {}
public data: T[] = [];
get top() {
return this.data.length;
}
get isEmpty() {
return this.top === 0;
}
get topElement() {
if (!this.top) return undefined;
return this.data[this.top - 1];
}
pop() {
return this.data.pop();
}
push(elem: T, ...args: any[]) {
throw 'Must implement `push` method!';
}
clear() {
this.data.length = 0;
return this.data;
}
}
class MonoDecreaseStack extends MonoStack<number> {
constructor(source: number[]) {
super();
this.source = source;
}
public source: number[]
push(elem: number, iterator: (elem: number) => void = function() {}) {
while(this.data.length && this.source[this.topElement] < this.source[elem]) {
iterator.call(this, this.data.pop());
}
this.data.push(elem);
}
}
function trap(height: number[]): number {
const stk = new MonoDecreaseStack(height);
return height.reduce((acc, elem, i) => {
stk.push(i, function(idx) {
if (this.topElement !== undefined) {
const top = height[this.topElement];
const cur = height[idx];
if (top !== cur) {
const dis = i - this.topElement - 1;
const depth = Math.min(elem, top) - cur;
acc += dis * depth;
}
}
});
return acc;
}, 0);
};
题解说明
找了两篇详细题解可以参考