单调栈

由于数据在栈内是单调递增或单调递减的，单调栈适合用来找出数组中第一个大于或小于某个元素的场景。元素出栈后，再根据题意对出栈元素进行处理，更新数据至 result。

标准模板

1. 第一个 for 循环内循环输入数组，
2. 第二个 for 循环维持栈内单调特性，不满足单调的元素依次出栈
3. 第一个 for 循环内对元素入栈

496. 下一个更大元素 I

直接输入出栈元素即可

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    //单调递减栈
    var stack,res []int
    //标准模板，首个元素先入栈
    stack = append(stack, 0)

    //由于只需要输出num1的元素，构造nums1的map作为需要输出数据的查询
    map1 := make(map[int]int)
    for i,v := range(nums1) {
        map1[v] = i
        //顺便初始化res，查不到的为-1
        res = append(res, -1)
    }
    for i:=1; i < len(nums2); i++ {
        // 单调递减，所以>=的都出栈
        for len(stack) > 0 && nums2[stack[len(stack)-1]] <= nums2[i] {
            // 查表，需要输出的加入res
            if idx, ok := map1[nums2[stack[len(stack)-1]]]; ok {
                res[idx] = nums2[i]
            }
            //pop
            stack = stack[:len(stack)-1]
        }
        // push
        stack = append(stack, i)
    }
    return res
}

42. 接雨水

出栈后计算出栈元素高度所在层的面积

/*

{2, 1, 0, 1, 3}
                  3
                +---+
  2             |   |
+---+           +   +
    | 1       1 |   |
    +---+   +---+   +
        | 0 |       |
  	    +---+       +
 0    1   2   3   4

 1. 按照下标0->1->2入栈
 2. 下标3入栈前依次对2->1进行出栈，出栈结束后下标0还在栈内
   a. 下标2出栈时，res += (min(height[3], height[1]) - height[2])*(3-1-1)
   b. 下标1出栈时，res += (min(height[3], height[0]) - height[1])*(3-0-1)
 3. 下标4入栈前依次对3进行出栈，res += (min(height[4], height[0]) - height[3])*(4-0-1)

res的加入是从右向左，按层的方式加入的
*/
// @lc code=start
func trap(height []int) int {
	var stack []int
	var res int
	min := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}
	stack = append(stack, 0)
	for i := 1; i < len(height); i++ {
		for len(stack) > 0 && height[i] >= height[stack[len(stack)-1]] {
			cachedTop := height[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break
			}
			res += (i - stack[len(stack)-1] - 1) * (min(height[i], height[stack[len(stack)-1]]) - cachedTop)

		}
		stack = append(stack, i)
	}
	return res
}

739. 每日温度

出栈后记录于外层循环中入栈元素下标的差值

func dailyTemperatures(temperatures []int) []int {
    //由于最后求idx的距离，stack存下标
    var stack []int
    //res不是按顺序append的（出栈的顺序）
    res := make([]int, len(temperatures))
    stack = append(stack, 0)
    for i:=1; i<len(temperatures);i++{
    //一直出栈，直到栈空或满足单调递减了
    //并做记录，写入res
        for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
            //记录出栈的位置，值为新入栈的位置减去出栈的位置
            res[stack[len(stack)-1]] = i - stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    //初始化时后面的数已经补零了
    return res
}

84. 柱状图中最大的矩形

与接雨水相反（接雨水算的是矩形外面的面积），这题算的是矩形的面积

func largestRectangleArea(heights []int) int {
	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}

	heights = append([]int{0}, heights...)
	heights = append(heights, 0)
	var res int
	//单调递增栈
	var stack []int
	stack = append(stack, 0)
	for i := 1; i < len(heights); i++ {
		for len(stack) > 0 && heights[i] < heights[stack[len(stack)-1]] {
			res = max(res, (i-stack[len(stack)-2]-1)*heights[stack[len(stack)-1]])
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}

	return res
}

769. 最多能完成排序的块 - 力扣（LeetCode）

子区间的最大值是单调递增的，因此栈保存每个子区间最大的元素值

• 新元素比栈顶元素大：入栈新区间
• 新元素比栈顶元素小：子区间最大值比新元素小的出栈（出栈的子区间合并到栈顶的子区间）

func maxChunksToSorted(arr []int) int {
	// 单调递增栈，存放各个子区间的最大值
	var stack []int
	stack = append(stack, arr[0])
	for i := 1; i < len(arr); i++ {
		if arr[i] > stack[len(stack)-1] {
			//若新元素比栈顶元素大， 入栈新区间的最大值
			stack = append(stack, arr[i])
		} else {
			//暂存最大的区间
			mx := stack[len(stack)-1]
			for len(stack) > 0 && arr[i] <= stack[len(stack)-1] {
				stack = stack[:len(stack)-1]
			}
			//重新入栈这个区间的最大值
			stack = append(stack, mx)
		}

	}
	return len(stack)
}