- 单调栈之基础题目
- 1.每日温度
- 1.1暴力解法
- 1.2单调栈方法(递减)
- 2.下一个更大的元素I
- 2.1暴力解法
- 2.2单调栈方法(递减)
- 3.下一个更大的元素II
- 3.1单调栈拼接数组(递减)
- 3.2单调栈(递减)
- 4.接雨水
- 4.1暴力解法(按列)
- 4.2备忘录优化/动态规划(按列)
- 4.3双指针(按列)
- 4.4单调栈(按行)(递减)
- 5.柱状图中的最大矩形
- 5.1暴力解法
- 5.2备忘录优化/动态规划
- 5.3双指针
- 5.4+单调栈(递增)(哨兵)
func dailyTemperatures(t []int) []int {
var res []int
for i := 0; i < len(t)-1; i++ {
j := i + 1
for ; j < len(t); j++ {
// 如果之后出现更高，说明找到了
if t[j] > t[i] {
res = append(res, j-i)
break
}
}
// 找完了都没找到
if j == len(t) {
res = append(res, 0)
}
}
// 最后一个肯定是 0
return append(res, 0)
}
1.2单调栈方法(递减)
// 单调递减栈
func dailyTemperatures(num []int) []int {
ans := make([]int, len(num))//必须得这样初始化，才能使ans[top]=0能进行下标这样的赋值；如果为0的话，就不用赋值了
stack := []int{}//
for i, v := range num {
// 栈不空，且当前遍历元素大于栈里的最后一个元素对的时候开始循环
//注意：这是个for循环，不是if循环，即如果取出最后一个元素的时候如果仍然大于，还会继续进行循环
for len(stack) != 0 && v > num[stack[len(stack)-1]] {
//1. 去除栈里最后一个元素的索引
top := stack[len(stack)-1]
//2. 索引差即可存到ans数组里，索引差(小标差就是两者之间的距离)即是
ans[top] = i - top
//3.出栈，即去除栈里最后一个元素
stack = stack[:len(stack)-1]
}
stack = append(stack, i)//栈里面存的是索引
}
return ans
}
//https://leetcode-cn.com/problems/daily-temperatures/solution/leetcode-tu-jie-739mei-ri-wen-du-by-misterbooo/
2.下一个更大的元素I 2.1暴力解法即栈底元素大，栈顶元素小
func nextGreaterElement(nums1 []int, nums2 []int) []int {
a := []int{}
for _, v := range nums1 {
j := 0
for ; j < len(nums2); j++ {
if v == nums2[j] {
break
}
}
j = j + 1
for ; j < len(nums2); j++ {
if nums2[j] > v {
a = append(a, nums2[j])
break
}
}
if j == len(nums2) {
a = append(a, -1)
}
}
return a
}
//时间复杂度：O(mn)，其中m是nums1的长度，n是nums2的长度
//空间复杂度：o(1)
2.2单调栈方法(递减)
func nextGreaterElement(nums1 []int, nums2 []int) []int {
res := make([]int, len(nums1))
for i:= range res {
res[i] = -1 //全部初始化为-1，原因是如果是-1的话，就不用对不符合的再赋值-1了
}
mp := map[int]int{}
//题目中说数组 nums1 和 nums2里没有重复元素
for i,v := range nums1 {
mp[v] = i //
}
// 单调栈
stack := []int{}
for i,v := range nums2 {
for len(stack) >0 && v> nums2[stack[len(stack)-1]] {
top := stack[len(stack)-1]
if _, ok := mp[nums2[top]]; ok { // 看map里是否存在这个元素
index := mp[nums2[top]] // 根据map找到nums2[top] 在 nums1中的下标
res[index] = v
}
stack = stack[:len(stack)-1] // 出栈
}
stack = append(stack, i)
}
return res
}
//时间复杂度：O(m + n)，其中 mm是nums1的长度，n 是nums 2的长度。我们需要遍历nums 2以计算nums2中每个元素右边的第一个更大的值；需要遍历 nums 1以生成查询结果。
//空间复杂度：O(n)，用于存储哈希表。
3.下一个更大的元素II
3.1单调栈拼接数组(递减)
func nextGreaterElements(nums []int) []int {
ans := make([]int, 2*len(nums))
for i := 0; i < 2*len(nums); i++ {
ans[i] = -1
}
stack := []int{}
add := append(nums, nums...) //不能写成add := append(nums, nums)，会报错
for i, v := range add {
for len(stack) != 0 && v > add[stack[len(stack)-1]] {
top := stack[len(stack)-1]
ans[top] = v
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
return ans[:len(nums)]
}
3.2单调栈(递减)
func nextGreaterElements(nums []int) []int {
length := len(nums)
result := make([]int, length)
for i := 0; i < len(result); i++ {
result[i] = -1
}
//单调递减，存储数组下标索引
stack := make([]int, 0)
for i := 0; i < length*2; i++ {
for len(stack) > 0 && nums[i%length] > nums[stack[len(stack)-1]] {
index := stack[len(stack)-1]
stack = stack[:len(stack)-1] // pop
result[index] = nums[i%length]
}
stack = append(stack, i%length)
}
return result
}
4.接雨水
4.1暴力解法(按列)
func trap(height []int) int {
if len(height) == 1 || len(height) == 2 {
return 0
}
ans := 0
//第一个柱子与最后一个柱子一定是0.所以不进行计算
for i := 1; i < len(height)-1; i++ {
leftmax := 0
rightmax := 0
//求左边最高柱子
for j := i; j >= 0; j-- {
leftmax = max(leftmax, height[j])
}
//求右边最高柱子
for j := i; j < len(height); j++ {
rightmax = max(rightmax, height[j])
}
ans += min(leftmax, rightmax) - height[i]
}
return ans
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
//时间复杂度为O(n^2),空间复杂度为O(1)
4.2备忘录优化/动态规划(按列)
func trap(height []int) int {
if len(height) == 1 || len(height) == 2 {
return 0
}
ans := 0
//定义备忘录
leftmax := make([]int, len(height))
rightmax := make([]int, len(height))
//初始化备忘录;
leftmax[0]=height[0]
rightmax[len(height)-1]=height[len(height)-1]
//从左向右进行计算；不用对最后一个元素进行赋值
for i := 1; i < len(height)-1; i++ {
leftmax[i]=max(leftmax[i-1],height[i])
}
//从右向左进行计算；即不用对第一个元素进行赋值
for i :=len(height)-2;i >=1 ;i--{
rightmax[i]=max(rightmax[i+1],height[i])
}
//leftmax与rightmax切片里的第一个元素与最后一个元素都用不上
for i := 1; i < len(height)-1; i++ {
ans += min(leftmax[i], rightmax[i]) - height[i]
}
return ans
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
//这个优化其实和暴力解法思路差不多，就是避免了重复计算，把时间复杂度降低为 O(N)，已经是最优了，但是空间复杂度是 O(N)
4.3双指针(按列)
func trap(height []int) int {
ans :=0
//left是左指针，只会向右移动; right是右指针，只会向左移动
left, right := 0, len(height)-1
//leftMax 是从左往右计算，rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组
leftMax := height[0]
rightMax := height[len(height)-1]
//注意：这种该方法再便利的时候其实是遍历到第一个元素与最后一个元素了，但是没有办法去除，只能这样
for left < right {
//leftmax是height[0]--height[left]中最高柱子的高度
leftMax = max(leftMax, height[left])
//rightmax是height[len(height-1)]--height[right]中最高柱子的高度
rightMax = max(rightMax, height[right])
if height[left] < height[right] {
ans += leftMax - height[left]
left++
} else {
ans += rightMax - height[right]
right--
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
4.4单调栈(按行)(递减)
func trap(height []int) (ans int) {
stack := []int{}
for i, h := range height {
for len(stack) > 0 && h > height[stack[len(stack)-1]] {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
//对于len以下这种情况，可以取ans里只有2个元素的情况下来讨论
if len(stack) == 0 {
break
}
left := stack[len(stack)-1]
curWidth := i - left - 1 //宽度
curHeight := min(height[left], h) - height[top] //高度
ans += curWidth * curHeight
}
stack = append(stack, i)
}
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
5.柱状图中的最大矩形
5.1暴力解法
func largestRectangleArea(heights []int) int {
res := 0 //结果
for i, v := range heights {
left := i
right := i
//找左边最后 1 个大于等于 heights[i] 的下标
for left > 0 && heights[left-1] >= v {
left--
}
// // 找右边最后 1 个大于等于 heights[i] 的索引
for right < len(heights)-1 && heights[right+1] >= v {
right++
}
width := right - left + 1
higth := v
s := width * higth
res = max(res, s)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
5.2备忘录优化/动态规划
func largestRectangleArea(heights []int) int {
res := 0 //结果
minleftindex := make([]int, len(heights)) //记录每个柱子 左边第一个小于该柱子的下标
minrightindex := make([]int, len(heights)) /// 记录每个柱子 右边第一个小于该柱子的下标
for i := 0; i < len(heights); i++ {
t := i - 1
//不断向左移动进行寻找
for t >= 0 && heights[t] >= heights[i] {
t = minleftindex[t]// 引用之前的查找更快,这就是备忘录的好处
}
minleftindex[i] = t //minleftindex[i] = -1
}
//只有倒着才能方便用备忘录规划
for i := len(heights) - 1; i >= 0; i-- {
t := i + 1
//不断向右移动进行寻找
for t < len(heights) && heights[t] >= heights[i] {
t = minrightindex[t]
}
minrightindex[i] = t //minrightindex[len(heights)-1]=len(heights)
}
for i := 0; i < len(heights); i++ {
s := heights[i] * (minrightindex[i] - minleftindex[i] - 1)
res = max(res, s)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
5.3双指针
func largestRectangleArea(heights []int) int {
res := 0 //结果
for i := 0; i < len(heights); i++ {
left := i
right := i
for ; left >= 0; left-- {
if heights[left] < heights[i] {
break
}
}
for ; right < len(heights); right++ {
if heights[right] < heights[i] {
break
}
}
width := right - left - 1
higth := heights[i]
res = max(res, width*higth)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
//如上代码并不能通过leetcode，超时了，因为时间复杂度是$O(n^2)$
5.4+单调栈(递增)(哨兵)
//注意：与下方式会出错，原因是当height里只有两个元素的时候会出错，比如[2,4]时res可能返回0；[4,2]时res也返回0(原因是l=0，1-0-1=0)
func largestRectangleArea(heights []int) int {
//单调栈（单调递增）
stack := make([]int, 0)
ln := len(heights)
res := 0 //结果
for i := 0; i < ln; i++ {
for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack) == 0 {
break
}
l := stack[len(stack)-1]
res = max(res, (i-l-1)*heights[top])
}
stack = append(stack, i)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
//正确方式:
func largestRectangleArea(heights []int) int {
//单调栈（单调递增）
stack := make([]int, 0)
stack = append(stack, -1) //stack的哨兵，方便确定左边界
heights = append(heights,0) //添加一个哨兵，减少代码量
ln := len(heights)
res := 0 //结果
for i:=0; i
//因为我们无法访问heights[-1]，所以限制len(stack) > 1
for len(stack) > 1 && heights[stack[len(stack)-1]] > heights[i] {
//栈顶元素，也就是当前要求的矩形柱子的下标
top := stack[len(stack)-1]
//出栈
stack = stack[:len(stack)-1]
//左边界（栈顶元素的后一个元素）
l := stack[len(stack)-1]
//矩形面积：(右边界-左边界-1) * 高度
//右边界就是i
//高度就是以栈顶元素为下标的柱子的高度
//左边界就是栈顶元素的下一位元素（因为我们添加了哨兵-1，所以这公式依旧成立）
res = max(res, (i-l-1)*heights[top])
}
stack = append(stack, i)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
递增分析
单调举例
特殊情况
