单调栈

发表于 更新于 分类于

单调栈

1. 定义

单调栈： 栈内元素是单调递增或单调递减的栈，只在栈顶进行操作。 时间复杂度为O(n) 即所有元素只进栈一次

性质：1). 栈具有单调性 2). 元素入栈前会把破坏单调性的元素出栈，

2. 详细示例以及算法解析

2.1 LC42 接雨水问题

业务场景为只要两个柱子之间形成凹槽，那么就可以存储水，也就是只要入栈的元素高度大于栈顶元素，那么就可以存水。 这是个单调递减栈，元素小于栈顶元素才可入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func trapV2(height []int) int {
	area := 0
	stack := list.New()
	for i := range height {
		for {
			top := stack.Front()
			if top == nil || height[i] < height[top.Value.(int)] {
				break
			}
			stack.Remove(top)
			bottom := top.Value.(int)

			// 如果栈顶的元素相同，那么只保留最后一个就可以，因为他们存储的大小一致
			for {
				if stack.Front() == nil || height[stack.Front().Value.(int)] != height[bottom] {
					break
				}
				stack.Remove(stack.Front())
			}

			// 将要入栈的元素大于栈顶元素 出栈并计算面积
			// 取两侧柱子的最小高度 - 已经计算的高度 = 剩下的可以被填充的高度
			if stack.Len() > 0 {
				top = stack.Front()
				area += (Min(height[i], height[top.Value.(int)]) - height[bottom]) * (i - top.Value.(int) - 1)
			}
		}
		stack.PushFront(i)
	}

	return area
}

2.1.1 暴力求解法

每个位置能存水的最大高度为当前注册两侧的最大值中的最小值减去当前柱子的高度，即为他能存水的高度。 伪代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13

for i := range heights {

	for j = 0 ; j <i; i ++ {
		leftMax = max(leftMax,height[j])
	}
	for j = i + 1 ; j < heights.len; i ++ {
		rightMax = max(rightMax,height[j])
	}

	area += min(leftMax,rightMax) - height[i]
}

2.1.2 动态规划法

该算法是在暴力破解法之上的优化，从上面的处理逻辑可以看到，计算所有两侧的告诉时，有很多都被重复计算，因此可以将中间结果记录下来
dp[i][0] 代表i左侧的最大高度
dp[i][1] 代表i右侧的最大高度
伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
l := len(height)
dp := []int{}
dp[0][0] = height[0] 
dp[l][1] = dp[l]
for i := range heights {

	if i > 0 {
		dp[i][0] = max(dp[i - 1][0],height[i])
	}
	if i < l {
		dp[i][1] = max(dp[i + 1][1],height[i])
	}

}

for i := range heights {

	area += min(dp[i][0],dp[i][1]) - height[i]
}


2.1.3 双指针移动法

左右双指针移动，柱矮的移动，（如果柱高的移动，那么会造成有部分没有计算，因为存水的面积是有柱子的高度决定的）。

由 area = min(dp[i][0] , dp[i][1]) - height[i] 得：

area = min(leftMax,rightMax) - height[i] , 所以让柱矮的移动，然后不断比对取两侧比较矮的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

left, right = 0, len(heights)
for {
	if left >= right {
		break
	}

	if leftMax < rightMax {
		leftMax = max(leftMax, heights[left])
		area += leftMax - height[left]
		left++
	}else {
		rightMax = max(rightMax, height[right])
		area += rightMax - heights[right]
		right--
	}
}
return area;

2.2 LC 84 柱状图中最大的矩形

同接雨水问题相关，如果入栈的元素小于栈顶元素，那么栈顶出栈并迭代计算当前的最大面积。 只有当元素大于栈顶元素时才入栈。
如果栈为空，那么代表元素的左侧都大于改元素，那么此时的左侧面积为 height[index] * i

否则左侧组成的面积大小为 height[index] * (i - left_i - 1), 原因： 左侧和右侧的元素一定都小于当前的height[index] 但是这俩之间的元素值一定大于当前的height[index],因为比它大的都出栈了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func largestRectangleArea(heights []int) int {

	// 末尾追加0，是因为如果是生序的话，保证最终能有个值兜底去计算其他的值
	heights = append(heights, 0)

	area := 0
	stack := list.New()
	for i := range heights {
		for {
			// 保持栈顶小于当前元素
			// 如果不小于，那么移除栈顶，计算当前高度的最大面积，否则直接入栈，因为添加了末尾元素0，所以即便是连续的递增，最终也会被计算
			f := stack.Front()
			if f == nil || heights[f.Value.(int)] < heights[i] {
				break
			}

			tArea := 0
			stack.Remove(f)

			// 获取当前的栈顶元素，来求解以当前为高度的元素的跨度
			top := f.Value.(int)
			if stack.Len() == 0 {
				tArea = heights[top] * i
			} else {
				tArea = heights[top] * (i - stack.Front().Value.(int) - 1)
			}
			if tArea > area {
				area = tArea
			}
		}
		stack.PushFront(i)
	}
	return area
}

2.2.1 暴力算法

计算以每个柱子为高，他能向外扩展的最大长度组成的矩形即为该柱可以形成的最大面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for i := range heights {

	left = i
	for j = i - 1; j >= 0 ; j-- {
		if height[j] > heights[i] {
			break
		}
		left = j
	}

	right = i
	for j = i + 1; j <= len(heights) ; j++ {
		if height[j] < heights[i] {
			break
		}
		right = j
	}
	area = (right - left + 1) * height[i]
}

2.2.2 分治法

分界点： 面积的大小是由所有柱子中最矮的决定的，所以我们以最矮的柱子为分界点

最大面积的分布又3种情况 1） 在左侧 2）在中间，通过中间联通两侧 3）在右侧

可以用分治的算法进行计算， 时间复杂度:
$$T(n) = 2(\frac {n} {2}) + O(logn) = O(nlogn)$$

1
2
3
4
5
6
7
8
9
10
device(heigths []int, left,right int) {
	if left > right {
		return 0
	}

	middle = findMin(heigths,left,right)

	return max((right-left + 1) * heigths[middle], device(heigths,left,middle - 1), device(middle+1,right))
}
return device(heigths,0,len(heigths)-1)