Algorithm Stack

记录 Stack 的算法实现

“32. Longest Valid Parentheses” Golang

func longestValidParentheses(s string) int {
    stack := make([]int, 0, len(s))
    stack = append(stack, -1)
    maxLen := 0

    updateMax := func(val int) {
        if val > maxLen {
            maxLen = val
        }
    }

    for i := 0; i < len(s); i++ {
        if s[i] == ')' {
            if stack[len(stack)-1] != -1 && s[stack[len(stack)-1]] == '(' {
                stack = stack[:len(stack)-1]
                updateMax(i - stack[len(stack)-1])
            } else {
                stack = append(stack, i)
            }
        } else {
            stack = append(stack, i)
        }
    }

    return maxLen
}

“84. Largest Rectangle in Histogram” Golang

func largestRectangleArea(heights []int) (ret int) {
    stack := []int{-1}

    max := func(val int) {
        if val > ret {
            ret = val
        }
    }

    for i := 0; i < len(heights); i++ {
        for stack[len(stack)-1] != -1 && heights[stack[len(stack)-1]] >= heights[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            max(heights[top] * (i - 1 - stack[len(stack)-1]) )
        }
        stack = append(stack, i)
    }

    for stack[len(stack)-1] != -1 {
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        max(heights[top] * (len(heights) - 1 - stack[len(stack)-1]))
    }

    return ret
}

“678. Valid Parenthesis String”

func checkValidString(s string) bool {
    var lStack, starStack []int
    for i, c := range s {
        if c == '(' {
            lStack = append(lStack, i)
        } else if c == '*' {
            starStack = append(starStack, i)
        } else if len(lStack) > 0 {
            lStack = lStack[:len(lStack)-1]
        } else if len(starStack) > 0 {
            starStack = starStack[:len(starStack)-1]
        } else {
            return false
        }
    }
    for i := len(lStack)-1; i >= 0; i-- {
        if len(starStack) > 0 && starStack[len(starStack)-1] > lStack[i] {
            starStack = starStack[:len(starStack)-1]
        } else {
            return false
        }
    }
    return true
}

“1063. Number of Valid Subarrays”

func validSubarrays(nums []int) (ret int) {
    nums = append(nums, -1)
    var stack []int
    for i, v := range nums {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > v {
            ret += i - stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    return ret
}