数据结构与算法-单调栈

Categories:

单调栈经典题目
单调递减栈
单调递增栈
1. 907. 子数组的最小值之和
2. 42. 接雨水

单调栈经典题目

单调递增栈（栈顶元素递增）：适用于找 左/右边第一个比当前值小的元素

单调递减栈（栈顶元素递减）：适用于找 左/右边第一个比当前值大的元素

单调递减栈

496. 下一个更大元素 I

func nextGreaterElement(nums1 []int, nums2 []int) []int {
	res := make([]int, len(nums1))
	nextGreater := make(map[int]int)
	var stack []int

	for _, num := range nums2 {
		for len(stack) > 0 && num > stack[len(stack)-1] {
			nextGreater[stack[len(stack)-1]] = num
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, num)
	}

	for i, num := range nums1 {
		if val, ok := nextGreater[num]; ok {
			res[i] = val
		} else {
			res[i] = -1
		}
	}

	return res
}

503. 下一个更大元素 II

func nextGreaterElements(nums []int) []int {
	n := len(nums)
	res := make([]int, n)
	for i := range res {
		res[i] = -1
	}

	var stack []int
	for i := 0; i < 2*n; i++ {
		num := nums[i%n]
		for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
			res[stack[len(stack)-1]] = num
			stack = stack[:len(stack)-1]
		}
		if i < n {
			stack = append(stack, i)
		}
	}

	return res
}

739. 每日温度

func dailyTemperatures(temperatures []int) []int {
	n := len(temperatures)
	res := make([]int, n)
	var stack []int

	for i := 0; i < n; i++ {
		for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
			pre := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res[pre] = i - pre
		}
		stack = append(stack, i)
	}
	return res
}

901. 股票价格跨度

write your code here

316. 去除重复字母

func removeDuplicateLetters(s string) string {
	last := make(map[rune]int)
	for i, c := range s {
		last[c] = i
	}

	var stack []rune
	inStack := make(map[rune]bool)

	for i, c := range s {
		if inStack[c] {
			continue
		}

		for len(stack) > 0 && c < stack[len(stack)-1] && last[stack[len(stack)-1]] > i {
			inStack[stack[len(stack)-1]] = false
			stack = stack[:len(stack)-1]
		}

		stack = append(stack, c)
		inStack[c] = true
	}

	return string(stack)
}

402. 移掉 K 位数字

func removeKdigits(num string, k int) string {
	var stack []byte

	for i := 0; i < len(num); i++ {
		// 当栈不为空，且当前数字小于栈顶数字，并且还有可以移除的数字
		for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] {
			stack = stack[:len(stack)-1] // 弹出栈顶元素
			k--
		}
		stack = append(stack, num[i]) // 将当前数字推入栈中
	}

	// 如果还有剩余的 k，移除栈末尾的元素
	for k > 0 {
		stack = stack[:len(stack)-1]
		k--
	}

	// 将栈中的数字拼接成字符串
	res := string(stack)

	// 去掉前导零
	for len(res) > 0 && res[0] == '0' {
		res = res[1:]
	}

	// 如果结果为空，返回 "0"
	if res == "" {
		return "0"
	}

	return res
}

581. 最短无序连续子数组

write your code here

456. 132 模式

write your code here

单调递增栈

907. 子数组的最小值之和

write your code here

42. 接雨水

func trap(height []int) int {
	if len(height) <= 0 {
		return 0
	}

	left, right := 0, len(height)-1
	leftMax, rightMax := height[left], height[right]
	res := 0

	for left < right {
		if height[left] < height[right] {
			if height[left] < leftMax {
				res += leftMax - height[left]
			} else {
				leftMax = height[left]
			}
			left++
		} else {
			if height[right] < rightMax {
				res += rightMax - height[right]
			} else {
				rightMax = height[right]
			}
			right--
		}
	}

	return res
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/15969090