# 示例来源: https://leetcode.cn/

示例 1：

输入：s = "()[]{}"
输出：true

示例 2：

输入：s = "(]"
输出：false

// 题解代码
func isValid(s string) bool {
	// 如果 s 的长度为奇数，肯定不是有效括号
	if len(s)&1 == 1 {
		return false
	}

	// 将左右边界字符进行分组并形成映射
	charMap := map[byte]byte{
		'(': ')',
		'{': '}',
		'[': ']',
	} 

	// 初始化栈
	var stack []byte

	for i := range s {
		if _, ok := charMap[s[i]]; ok {
			// 左边界组的字符直接入栈
			stack = append(stack, s[i])
		} else {
			// 右边界组的字符与栈顶元素进行比较
			index := len(stack) - 1
			if len(stack) == 0 || s[i] != charMap[stack[index]] {
				return false
			}
			stack = stack[:index]
		}
	}

	// 此时栈内可能还存在一些左边界字符
	// 所以需要判断栈是否为空
	return len(stack) == 0
}

# 示例来源: https://leetcode.cn/

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9


示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

// 题解代码
func evalRPN(tokens []string) int {
	if len(tokens) == 0 {
		return 0
	}

	var stack []int

	for _, token := range tokens {
		// 将当前 token 解析为数字
		val, err := strconv.Atoi(token)

		// 如果没有发生错误
		// 说明当前 token 为数字，直接入栈
		if err == nil {
			stack = append(stack, val)
		} else {
			// 说明当前 token 为运算符
			// 取出栈顶的两个数字
			num1, num2 := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]

			// 根据不同的运算符执行不同的计算
			// 同时将计算结果加入到栈中s
			switch token {
			case "+":
				stack = append(stack, num1+num2)
			case "-":
				stack = append(stack, num1-num2)
			case "*":
				stack = append(stack, num1*num2)
			case "/":
				stack = append(stack, num1/num2)
			}
		}
	}

	// 返回栈底元素
	return stack[0]
}

# 示例来源: https://leetcode.cn/

示例 1：

输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 2：

输入：path = "/a/./b/../../c/"
输出："/c"

// 题解代码
func simplifyPath(path string) string {
	var stack []string

	for _, p := range strings.Split(path, "/") {
		// 无效路径字符，直接跳过
		if p == "" || p == "." {
			continue
		}

		// 目录名称/文件名称 入栈
		if p != ".." {
			stack = append(stack, p)
		} else if p == ".." && len(stack) > 0 {
			// 如果是上级目录 ..
			// 将栈顶元素出栈
			stack = stack[:len(stack)-1]
		}
	}

	return "/" + strings.Join(stack, "/")
}

func Solution(nums []int) {
	// 1. 初始化单调栈
	stack := make([]int, 0)

	// 2. 遍历数组
	for i := range nums {
		// 这里的示例为 单调递增栈

		// 维护栈的单调性
		for len(stack) > 0 && nums[i] < nums[stack[len(stack)-1]] {
			// 获取栈顶元素
			index := stack[len(stack)-1]
			// 栈顶元素出栈
			stack = stack[:len(stack)-1]

			// 使用栈顶元素更新问题逻辑解或者做相应的处理
			...
		}

		// 维护单调递增栈，将元素的索引入栈
		stack = append(stack, i)
	}

	// 根据题目要求确定是否处理栈中剩余元素
	for len(stack) > 0 {
		...
	}
}

# 示例来源: https://leetcode.cn/

示例 1：

输入：prices = [8,4,6,2,3]
输出：[4,2,4,2,3]
解释：
商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。
商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。
商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。
商品 3 和 4 都没有折扣。


示例 2：

输入：prices = [1,2,3,4,5]
输出：[1,2,3,4,5]
解释：在这个例子中，所有商品都没有折扣。

// 题解代码
func finalPrices(prices []int) []int {
	n := len(prices)
	res := make([]int, n)

	// 1. 初始化单调栈
	// 因为只需要计算折扣后的值
	// 所以栈内存储数组值就可以
	// 栈顶始终保留一个值 0 作为 “哨兵”
	// 避免边界检查，同时表示语义: “没有折扣”
	stack := []int{0}

	// 2. 遍历数组
	// 题目声明，享受折扣时的索引必须比当前索引大
	// 也就是说，数组中的最后一件商品价格无法享受任何优惠
	// 所以数组从后向前遍历即可
	for i := n - 1; i >= 0; i-- {
		// 当前栈内的商品价格依次递增，符合单调递增的特性
		// 也就是说，如果一个商品价格出现在栈内
		// 说明还未找到 该商品价格 对应的 折扣价格

		// 3. 维护单调递增性
		// 如果 栈顶商品价格 比 当前商品价格 大，说明当前单调递增性已经被破坏
		// 那么此时就可以开始给当前商品 寻找对应的 折扣价格 了
		// 弹出栈顶商品价格，直到遇到比 当前商品价格 小的 商品价格(折扣价格)
		for len(stack) > 1 && stack[len(stack)-1] > prices[i] {
			stack = stack[:len(stack)-1]
		}

		// 4. 处理具体逻辑

		// 此时 栈顶商品价格 就是 当前商品价格 可以享受的折扣
		// 更新即可
		res[i] = prices[i] - stack[len(stack)-1]

		// 将当前商品价格入栈
		stack = append(stack, prices[i])
	}

	return res
}

# 示例来源: https://leetcode.cn/

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

// 题解代码
func dailyTemperatures(temperatures []int) []int {
	res := make([]int, len(temperatures))

	// 1. 初始化单调栈
	// 因为题目要求寻找 “下一个” 更高的温度对应的索引 (间隔天数)
	// 所以栈内存储数组索引
	var stack []int

	// 2. 遍历数组
	for i := range temperatures {
		// 当前栈内索引对应的温度依次递减，符合单调递减的特性
		// 也就是说，如果一个索引出现在栈内
		// 说明还未找到该索引对应的温度 的  “下一个” 更高的温度

		// 3. 维护单调递减性
		// 如果当前元素温度 大于 栈顶元素温度
		// 说明当前单调递减性已经被破坏
		// 那么当前元素就是 “下一个” 更高的温度
		for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
			// 4. 处理具体逻辑

			// 获取栈顶元素索引
			preIndex := stack[len(stack)-1]
			// 栈顶元素出栈
			stack = stack[:len(stack)-1]

			// 更新栈顶元素索引对应的温度 的  “下一个” 更高的温度
			// 因为题目要求寻找 “下一个”  更高的温度在几天后
			// 所以这里使用当前索引 减去 栈顶索引
			// 得出的差值就是中间的间隔天数
			res[preIndex] = i - preIndex
		}

		// 将当前元素的索引入栈
		stack = append(stack, i)
	}

	return res
}

// 题解代码
func trap2(height []int) int {
	res := 0

	// 1. 初始化单调栈
	// 栈内存储数组索引
	var stack []int

	// 2. 遍历数组
	for i := range height {
		// 当前栈内索引对应的柱子依次递减，然后寻找右侧 “更高的柱子” 用来蓄水
		// 符合单调递减的特性
		// 也就是说，如果一个索引出现在栈内
		// 说明还未找到该索引对应的柱子 的右侧 “更高的柱子”

		// 3. 维护单调递减性
		// 如果当前柱子高度 大于 栈顶元素高度
		// 说明当前单调递减性已经被破坏
		// 那么当前元素就是 右侧 “更高的柱子”
		for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
			// 4. 处理具体逻辑

			// 获取栈顶元素索引
			top := stack[len(stack)-1]
			// 栈顶元素出栈
			stack = stack[:len(stack)-1]

			// 如果栈内只有一个元素
			// 那么此时 stack 的长度等于 0
			// 也就说明此时才刚刚找到 “左边的柱子”
			// 还没有找到 “右边的柱子”
			// 比如这种情况 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
			// 当 i 为 1 时，左边的柱子 (栈顶元素) 是 0
			// 这时接不到任何雨水，所以无需计算
			if len(stack) > 0 {
				left := stack[len(stack)-1]

				// 左右两个柱子之间的距离
				w := i - left - 1
				// 左右两个柱子之间的高度，以较低的为准，“木桶原理”
				h := min(height[i], height[left]) - height[top]

				// 将左右两个柱子之间的面积 (也就是蓄水容量) 累积到总计值
				res += w * h
			}
		}

		stack = append(stack, i)
	}

	return res
}