IT博客汇 | 『代码随想录』单调栈（Monotonic Stack）

『代码随想录』单调栈（Monotonic Stack）

NX の博客发表于 2023-12-22 07:23:55

DAY 58

每日温度

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    stack := make([]int, 0, n)
    ans := make([]int, n)
    for i, temperature := range temperatures {
        for len(stack) > 0 && temperature > temperatures[stack[len(stack)-1]] {
            ans[stack[len(stack)-1]] = i - stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    return ans
}

下一个更大元素 I

不同之处是栈中存的是元素的值

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    stack := make([]int, 0, len(nums2))
    m := map[int]int{}
    for _, num := range nums2 {
        for len(stack) > 0 && num > stack[len(stack)-1] {
            m[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, num)
    }
    ans := make([]int, 0, len(nums1))
    for _, num := range nums1 {
        val, ok := m[num]
        if !ok {
            ans = append(ans, -1)
        } else {
            ans = append(ans, val)
        }
    }
    return ans
}

DAY 59

下一个更大元素 II

复制一份即可

func nextGreaterElements(nums []int) []int {
    nums = append(nums, nums...)
    n := len(nums)
    ans := make([]int, n)
    for i := range ans {
        ans[i] = -1
    }
    stack := make([]int, 0, n)
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            ans[stack[len(stack)-1]] = nums[i]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    return ans[:n/2]
}

接雨水

提前找出当前元素左右两边的最高元素，感觉还是双指针简单

func trap(height []int) (ans int) {
    n := len(height)
    if n == 0 {
        return
    }

    leftMax := make([]int, n)  // 当前及左边的最大高度
    rightMax := make([]int, n) // 当前及右边的最大高度
    leftMax[0] = height[0]
    rightMax[n-1] = height[n-1]

    for i := 1; i < n; i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }

    for i := n - 2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }

    for idx, h := range height {
        ans += min(leftMax[idx], rightMax[idx]) - h
    }

    return
}

DAY 60

柱状图中最大的矩形

func largestRectangleArea(heights []int) int {
    heights = append(heights, 0)
    n := len(heights)
    stack := []int{}
    ans := 0

    for i := 0; i < n; i++ {
        for len(stack) > 0 && heights[i] < heights[stack[len(stack)-1]] {
            curr := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            area := (i - left - 1) * heights[curr]
            if area > ans {
                ans = area
            }
        }
        stack = append(stack, i)
    }

    return ans
}