代码随想录:单调栈

发布时间:2024年01月05日

单调栈

单调栈是一种特殊的栈结构,通常用于解决一类特定的问题,如找到数组中元素的下一个更大(或更小)元素。它的核心特性是维护栈内元素的单调性,即栈内元素按照从栈底到栈顶的顺序,要么严格递增,要么严格递减

739. Daily Temperatures

思路:
遍历所有元素,依次压入栈! 但要保持栈是单调递减!

如何做到单调性?
每次压入一个元素tem[i]的时候和栈顶元素比较,

  1. 如果小于等于栈顶元素直接压入;
  2. 如果大于栈顶元素,进行标记后压入栈,说明找到了大于栈顶的元素,且它为第一个!

如何标记?给谁标记?
在栈顶元素的索引位置,记录该元素的与栈顶索引距离。
给栈顶元素标记当前元素,表示栈顶元素右侧第一个大于自己的就是当前元素。

举例:nums= [5, 4, 3, 5], 依次压入栈中 stack=[5,4,3],

i=3nums[4]stack.top()
53

假如当前i=3,当前元素 > 栈顶元素。 然后计算两者的索引距离 3 - 2 = 1.

在栈顶元素的索引位置记录下来这个值。[0, 0, 1, 0]
然后弹出栈顶的元素 stack = [5, 4] ,
继续重复判断,该元素大不大与上一个元素?如果是的话,就给上一个元素标记。
直到该元素不大于栈顶元素了,把该元素压入栈

为了理解 上面栈中写的是元素,其实代码中 栈记录的是索引

go语言实现

/**
 * @date: 2024 Jan 04
 * @time: 22:10
 * @author: Chris
 * @title: 739. Daily Temperatures
 * @link: https://leetcode.cn/problems/daily-temperatures/description/
**/
package day58

// 找右侧第一个大于该元素的值。
// [4, 1, 5, 9] 第一个大于4的值为5,第一个大于1的也为5
// 答案 [5, 5, 9, -1]
// 栈中元素是单调的,递增或递减
func dailyTemperatures(temperatures []int) []int {
	result := make([]int, len(temperatures))

	for i := range result {
		result[i] = 0
	}

	var stack []int

	for i, tem := range temperatures {
		// 非空栈,  当前元素 >  栈顶元素
		for len(stack) > 0 && tem > temperatures[stack[len(stack)-1]] {

			topIndex := stack[len(stack)-1]
			// 就找到了大于栈顶的元素!且它是第一个大于栈顶的!
			// 给栈顶元素标记一下,该元素的位置!
			result[topIndex] = i - topIndex 
			
			stack = stack[:len(stack)-1] // 已经记录完了,弹出栈
			
		}
		// 把数组中的每一个元素(的索引)都加入栈中
		stack = append(stack, i)
	}
	return result
}

496. Next Greater Element

步骤很简单,
第一步,使用单调栈找nums2的右侧第一个大的元素,并记录下来
第二步,根据nums1查找第一步的记录表,然后写入result数组!

/**
 * @date: 2024 Jan 04
 * @time: 23:35
 * @author: Chris
 * @title: 496. Next Greater Element
 * @link: https://programmercarl.com/0496.下一个更大元素I.html
**/

package day58

// nums2用单调栈找到右侧第一个最大的值,并用map记录结果
// 然后映射给nums1
func nextGreaterElement(nums1 []int, nums2 []int) []int {
	stack := []int{}

	// map = (栈顶元素 : 右侧第一个大于自己的元素)
	nextGreater := make(map[int]int)

    // 根据单调栈的步骤,记录下来,
	// 因为题目中要求是nums1中元素在nums2中元素xxxx,
	// 所以这里这里记录的是元素-元素的映射,不是索引-元素。
	for _, num := range nums2 {
		for len(stack) > 0 && num > stack[len(stack)-1] {
			top := stack[len(stack)-1]
			nextGreater[top] = num
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, num)
	}

	// 栈里的元素都是不存在 右侧 大于自己的元素
	for len(stack) > 0 {
		top := stack[len(stack)-1]   // 栈顶元素
		nextGreater[top] = -1        //  置为-1
		stack = stack[:len(stack)-1] //出栈
	}

	// 记录答案
	result := make([]int, len(nums1))
	for i, num := range nums1 {
		result[i] = nextGreater[num] // 查表
	}
	return result
}
文章来源:https://blog.csdn.net/weixin_43356770/article/details/135398242
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。